876. Middle of the Linked List

Algorithm

本周做的算法题是 876. Middle of the Linked List。

问题描述

给一个非空的链表，找到其中间节点。若有两个中间节点，返回第二个。例子：

1. [1,2,3,4,5] 返回 3

2. [1,2,3,4,5] 返回 4

思路

1. 将遍历链表，将元素放入一个数组arr里面，然后直接返回arr[len/2],时间复杂度是O(len)（链表长度），空间复杂度O(len)。

2. 快慢指针法，快慢指针遍历链表，快的比慢多走一倍。快指针遍历完链表，慢指针就是中间节点。时间复杂度O(len)（链表长度），空间复杂度O(1)。

public ListNode middleNode(ListNode head) {
    if (null == head) {
        return null;
    }
    ListNode fastNode = head;
    ListNode slowNode = head;
    
    while (fastNode != null && fastNode.next != null) {
        fastNode = fastNode.next.next;
        slowNode = slowNode.next;
    } 
    return slowNode;
}