LeetCode题解—求链表的中间结点

题目：求链表的中间结点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：输入：[1,2,3,4,5] 输出：此列表中的结点 3

(序列化形式：[3,4,5]) 返回的结点值为 3 。

(测评系统对该结点序列化表述是 [3,4,5])。注意，我们返回了一个 ListNode 类型的对象 ans，这样：ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：输入：[1,2,3,4,5,6] 输出：此列表中的结点 4

(序列化形式：[4,5,6])

由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

解法一

题目意思还是比较简单的，就是找到中间结点。

首先想到的就是先算出来链表总长度，然后再遍历到中间结点就可以了：

public ListNode middleNode(ListNode head) {
        int n = 0;
        ListNode cur = head;
        while (cur != null) {
            n++;
            cur = cur.next;
        }
        int k = 0;
        cur = head;
        while (k < n / 2) {
            k++;
            cur = cur.next;
        }
        return cur;
    }

时间复杂度

一共遍历了1次加半次。去除常量，时间复杂度为O(n)

空间复杂度

只用到单独的一个链表结点，空间复杂度为O(1)

解法二

还记得上一篇我们说到的找到结尾第n个结点算法题吗？其中用到了一个叫做快慢指针的解法。

在这里依然可以用到。可能你就有疑惑了，上一次是知道两个指针之间相隔n个结点，这一次怎么用呢？

如果我们将慢指针每次移动一格，快指针每次移动两格，那么快指针是不是每次都是慢指针的两倍步数呢？

这样当快指针移到尾部的时候，慢指针就刚好在中间结点了。

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;
    }

这里因为每次fast都要移动两步，所以需要判断当前结点和下一个结点是否都为空。

slow 1  2  3  4  5  6  
fast 1  3  5  7  9  11  

上面的例子就是快慢指针会走到的节点数：

• 如果链表为奇数，比如[1,2,3,4,5]，那么刚好快慢结点就会走到3和5。
• 如果链表为奇数，比如[1,2,3,4,5,6]，那么刚好快慢结点就会走到4和null。

时间复杂度

用到了遍历，所以时间复杂度还是O(n)

空间复杂度

空间复杂度为O(1)

其他解法

如果该题是数组的话，是不是一句代码就能解出来呢？Array[n/2]。所以我们完全可以将链表转化成数组，然后一句代码就可以输出中间结点数了，你可以动手试试哦。

这种解法的时间复杂度和空间复杂度又是多少呢？

参考

https://leetcode-cn.com/problems/middle-of-the-linked-list/