LeetCode每日一题：3.23链表的中间节点（七十九）

链表的中间节点

一、LeetCode题解

瞧一瞧～

• 博健的LeetCode题解：Gitbook版本传送门
• 博健的LeetCode题解：CSDN传送门
• 有趣的CSS：Gitbook传送门
• 前端进阶笔记：Gitbook传送门

二、算法题

题目

给定一个带有头结点 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，我们返回第二个结点。

解法一 （数组）

思路

• 链表是无法直接通过下标查询的，所以我们借助一个辅助数组来保存链表内的数据。
• 时间复杂度：O(N)，其中遍历整个链表。
• 空间复杂度：O(N)，创建了保存所有数据的数组。

代码

var middleNode = function(head) {
    var node = head, arr = [],len = 0
    while(node){
        arr[len++] = node
        node = node.next
    }
    return arr[arr.length >> 1] //向右移1位 = /2&&向上取整
};

结果

解法二（单指针）

思路

• 解法一是利用数组记录所有数据，这一次我们利用指针统计链表的个数
• 第一次统计个数
• 第二次返回所需节点
• 时间复杂度：O(N) ，遍历整个数组2次
• 空间负责度：O(1)

代码

var middleNode = function(head) {
    var len = 0, cur = head
    while(cur){
        len++
        cur = cur.next
    }
    var mid = len >> 1
    var k = 0
    cur = head
    while(k < mid){
        k++
        cur = cur.next
    }
    return cur
};

结果

解法三（快慢指针）✅

思路

我们可以优化一下解法二

• 建立一个慢指针1次走1步
• 建立一个快指针1次走2步
• 当快指针走到终点时，慢指针一定走到一半处。
• 时间复杂度：O(N)，其中 N是给定链表的结点数目。
• 空间复杂度：O(1)，只需要常数空间存放 slow 和 fast 两个指针。

代码

var middleNode = function(head) {
    var slow = head, fast = head;
    while(fast && fast.next){
        slow = slow.next
        fast = fast.next.next
    }
    return slow
};

结果