leetcode Linked List

leetcode 876题

Posted by franki on November 25, 2020

leetcode 876题 链表的中间结点

给定一个头结点为 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 循环链表依次放入到数组里面，数组的长度就是链表的长度，最后获取中位数，返回数组的中位数即可

2 使用两次循环，第一次算出链表的长度，第二次循环找出中位的节点

3 使用快慢指针，慢指针每次前进一步，快指针每次前进两步，当快指针到达结尾时，慢指针刚好走到中点

代码

var middleNode = function(head) {
    const arr = [];
    let curr = head;
    while (curr) {
        arr.push(curr);
        curr = curr.next;
    }
    const mid = Math.floor(arr.length / 2);
    return arr[mid];
};

function middleNode(head) {
    let n = 0;
    let curr = head;
    while (curr) {
        n++;
        curr = curr.next;
    }

    let k = 0;
    curr = head;
    while (k++ < Math.floor(n / 2)) {
        curr = curr.next;
    }
    return curr;
}

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

复杂度分析

  • 时间复杂度: O(N) O(N) O(n)
  • 空间复杂度: O(n) O(1) O(1)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList 复盘 QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python SVG
    FRIENDS