Leetcode daily practice - 876. Intermediate node of linked list

Preface

Wassup guys！ I am a Edison

It's today LeetCode Upper leetcode 876. The middle node of a list

Let’s get it！

---

---

1. Topic analysis

Given a header node as head The non empty single chain table of , Returns the middle node of the linked list .
 
If there are two intermediate nodes , Then return to the second intermediate node .

Example 1：

Example 2：

2. Title diagram

The method used in this problem is Fast and slow pointer method ;

（1） Define slow pointer slow One go 1 Step ;
 
（2） Define fast pointers fast One go 2 Step ;

Odd numbers

When the linked list is Odd number Time , First ,slow and fast All point to the first node （ As shown in the figure ）

then slow One go 1 Step ,fast One go 2 Step , Dynamic diagram demonstration

When fast Go to the Tail node When ,slow It points to Intermediate nodes

Even numbers

When the linked list is even numbers Time , First ,slow and fast All point to the first node （ As shown in the figure ）

then slow One go 1 Step ,fast One go 2 Step , Dynamic diagram demonstration

You can see , When fast Go to the NULL when ,slow It points to Intermediate nodes ;

summary ：

（1） When the number of nodes in the linked list is Odd number when , The condition for the end of the loop is fast Go to the Tail node ;
 
（2） When the number of nodes in the linked list is even numbers when , The condition for the end of the loop is fast Go to the NULL;

3. Code implementation

Interface code

struct ListNode* middleNode(struct ListNode* head){
    
    struct ListNode* slow, *fast;
    slow = fast = head
    while (fast && fast->next) {
    
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

Submit results

One more thing to note ： stay while Loop judgment section , It's a condition for continuation , Think about the conditions for the end ！