[summary of linked list skills] 876. Intermediate node of linked list

876. The middle node of a linked list

One 、 subject

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 .
 

Tips ：

The number of nodes in a given list is between  1  and  100  Between .

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/middle-of-the-linked-list
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Two 、 Problem solving

Ideas ：

The key to the problem is that we can't get the length of the single linked list directly n, The conventional method is to traverse the linked list first n, Traverse again to get the second n / 2 Nodes , That is, the intermediate node .

If you want to traverse once, you can get the intermediate node , You also need to be smart , Use 「 Speed pointer 」 The technique of ：

Let's make two pointers slow and fast Respectively point to the chain header node head.

Whenever the pointer is slow slow Take a step forward , Quick pointer fast Just two steps forward , such , When fast When you get to the end of the linked list ,slow It points to the midpoint of the linked list .

ListNode middleNode(ListNode head) {
    //  The speed pointer initializes to  head
    ListNode slow = head, fast = head;
    //  The pointer stops when it comes to the end 
    while (fast != null && fast.next != null) {
        //  Slow pointer one step , Let's go two steps 
        slow = slow.next;
        fast = fast.next.next;
    }
    //  The slow pointer points to the midpoint 
    return slow;
}

It should be noted that , If the length of the list is even , That is to say, when there are two midpoint , The node returned by our solution is the later node .

Force to buckle 876 topic 「 The middle node of a list 」 You can directly apply this solution .

in addition , With a little modification, this code can be directly used to judge the algorithm problem of linked list forming a ring .

Code ：

    /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };

 It should be noted that , If the length of the list is even , That is to say, when there are two midpoint , The node returned by our solution is the later node .

 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast != NULL&&fast->next != NULL){
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};