“This is the 12th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Topic describes

Given a non-empty singly linked list with head, return the middle node of the list.

If there are two intermediate nodes, the second intermediate node is returned.

  • Example 1:

Input: [1,2,3,4,5] output: node 3 in this list (serialized form: [3,4,5]) returns the value of node 3. (the serialization statement of this node in the evaluation system is [3,4,5]). Val = 3, ans.next-val = 4, ans.next-next-val = 5, and ans.next-next-next = NULL.

  • Example 2:

Input: [1,2,3,4,5,6] output: node 4 in this list (serialized form: [4,5,6]) since the list has two intermediate nodes with values of 3 and 4, we return the second node.

  • Tip:
  1. The number of nodes in a given linked list is between1 和 100In between.

Subject analysis

The fast pointer takes two steps at a time, and the slow pointer takes one step at a time. When the fast pointer is finished, the slow pointer just reaches the middle position and returns to the slow pointer.

Case 1: If there are an odd number of nodes (2n+1), the fast pointer needs to be traversed for (2n+1-1)/2 = n times. For 2n+1 nodes, the intermediate node is the NTH node. In this case, the slow node advances exactly N steps, and the node to which the slow pointer points is directly returned.

Situation 2: If it is an even number of nodes (if it is 2n), according to the rule, if the fast pointer takes two steps every time, it will fall on the nodes with odd points. For the fast pointer, we assume that we need to take x steps, and the end, then 2n< 2x+1 <2(n+1) => n-1/2< x <n+1/2 If x is an integer, x is n. According to the description in the problem, If it is an even number of points, the node after the middle two nodes is taken, that is, the node corresponding to n+1, so the slow pointer is taken as the subscript after it.

Note that not only is fast not empty, but fast. Next is not empty. Otherwise go to the last node, fast also back access will throw the wrong.

Time complexity: O(N) where N is the length of the array.

Space complexity: O(1), only constant space is needed to store two Pointers slow and fast.

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode middleNode(ListNode head) { if (head == null) return null; ListNode fast = head, slow = head; while(fast! =null&&fast.next! =null){ fast = fast.next.next; slow = slow.next; } return slow; }}Copy the code

\