链表的中间结点

• 在线：LeetCode: 876

题目

Given a non-empty, singly linked list with head node head, return a middle node of linked list.If there are two middle nodes, return the second middle node.

JavaScript

function ListNode(val) {
  this.val = val;
  this.next = null;
}

Python

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

思路

双指针。让快指针两步两步走，同时慢指针一步一步走，当快指针走到末尾时，慢指针便指向了中间结点。

Solution 1

如果快指针可以前进的条件是：当前快指针和当前快指针的下一个结点都非空。

while fast and fast.next:
    fast = fast.next.next
    sLow = slow.next

当结点个数为奇数时，slow 结点落在链表的中间结点：

当结点个数为偶数时： slow 结点落在靠右的中间结点（符合题意）：

Solution 2

如果快指针可以前进的条件是：当前快指针下一个结点和下下个结点都非空。

while fast.next and fast.next.next:
    slow = slow.next
    fast = fast.next.next

当结点个数为奇数时，slow 结点落在链表的中间结点：

当结点个数为偶数时： slow 结点落在靠左的中间结点（ 不符合题意）：

代码实现

JavaScript

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var middleNode = function (head) {
  let fast = head;
  let slow = head;
  while (fast && fast.next) {
    fast = fast.next.next;
    slow = slow.next;
  }
  return slow;
};

Python

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        fast = head
        slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        return slow

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(1)

参考资料

1. 快慢指针 by liweiwei1419