【基础篇 - Day 25】 2023-03-09 - 876. 链表的中间结点 （05. 双指针）

[threedayAAAAA]

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

提示：

给定链表的结点数介于 1 和 100 之间。

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/middle-of-the-linked-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[threedayAAAAA]

思路

快慢指针

代码

function middleNode(head: ListNode | null): ListNode | null {
    let fast = head
    let slow = head
    while(fast?.next){
        fast = fast?.next?.next
        slow = slow?.next
    }
    return slow
};

时空复杂度

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

[MiumMi]

思路

快慢指针

代码

function middleNode(head: ListNode | null): ListNode | null {
    if (!head || !head.next) {
        return head;
    }
    let slow = head;
    let fast = head;
    while (fast?.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
};

---

分析

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

[yunliuyan]

思路

• 快慢指针
• 当快指针跑到链尾，慢指针就在中间

代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
// 快慢指针，快指针到链表尾部，慢指针正好在中间
function middleNode(head: ListNode | null): ListNode | null {
    let slow = head, fast = head;
    while(fast?.next) {
        slow = slow.next;
        fast = fast.next?.next;
    }
    return slow;
};

复杂度分析

时间复杂度: O(n)

空间复杂度: O(1)