定义:
用两个指针 slow
与 fast
一起遍历链表。slow
一次走一步,fast
一次走两步。
那么当 fast
到达链表的末尾时,slow
必然位于中间。
例题:
给定一个头结点为 head
的非空单链表,返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。
题解:
1 class Solution { 2 public ListNode middleNode(ListNode head) { 3 ListNode slow = head, fast = head; 4 while (fast != null && fast.next != null) { 5 slow = slow.next; 6 fast = fast.next.next; 7 } 8 return slow; 9 } 10 }