[leetcode ladder] linked list · 876 find the middle node of the linked list

Title Description ：

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：

 Input ：[1,2,3,4,5]
 Output ： Nodes in this list  3 ( Serialization form ：[3,4,5])
 The returned node value is  3 . ( The evaluation system expresses the serialization of this node as follows  [3,4,5]).
 Be careful , We returned one  ListNode  Object of type  ans, such ：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5,  as well as  ans.next.next.next = NULL.

Example 2：

 Input ：[1,2,3,4,5,6]
 Output ： Nodes in this list  4 ( Serialization form ：[4,5,6])
 Because the list has two intermediate nodes , Values, respectively  3  and  4, Let's go back to the second node .

Topic link ：

876. The middle node of a list - Power button （LeetCode）https://leetcode.cn/problems/middle-of-the-linked-list/submissions/

---

Their thinking ：

Conventional method 1： Speed pointer

This is a classic topic , Use the speed pointer . Among them, the fast pointer takes two steps at a time , Slow pointer one step at a time , When the fast pointer goes empty , The slow pointer is just halfway .

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* slow=head;
    if(head==NULL) // If it is an empty list , that fast It didn't exist at first 
        return NULL;
    struct ListNode* fast=head->next;
    while(fast)
    {
        fast=fast->next; // Whether it is an even number of nodes or an odd number of nodes ,fast There will be no null pointer in the penultimate step of 
        if(fast!=NULL) // At the last step ,fast May already be empty , At this time, there is no need to take another step backwards 
            fast=fast->next;
        slow=slow->next; //slow One step back at a time 
    }
    return slow;
}

To sum up ： Here we use the operation of fast and slow pointer to find the intermediate node , But there are two aspects of this method that deserve attention ：

• The first point is when the original linked list is an empty linked list , I can't find it fast The position of the initial pointer of , If directly executed fast=head->next; Null pointer errors may occur .
• The second point is in the process of loop traversal ,fast The pointer enters in the last two steps NULL when , When the original linked list has an even number of nodes , The penultimate step has entered NULL 了 , At this point, if you directly execute the second fast=fast->next; Null pointer errors still occur .

So is there any way to simplify this operation ？ That's for sure ！

Conventional method 2： Improved version of fast and slow pointer

In fact, we can improve the two characteristics of the first method , The first is the first point , At the beginning , We might as well fast Pointers and slow All point to head, In this way, you don't have to specially consider the case that the original linked list is empty ,fast Point to NULL->next situation . But changed this , At the same time, we need to modify the end condition of the loop , We can find even and odd nodes by plotting slow When pointing to the intermediate node fast End position ：

• When the number of linked list nodes is odd ：fast->next by NULL End traversal .
• When the number of linked list nodes is even ：fast by NULL End traversal .

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* slow = head; // The speed pointer points to the first node of the linked list 
    struct ListNode* fast = head;
    while(fast&&fast->next) // As long as one of these two is satisfied NULL, explain slow It points to the middle node of the linked list 
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}