【LeetCode】21. Middle of the Linked List· 链表的中间节点

题目描述

英文版描述

Given the head of a singly linked list, return the middle node of the linked list. If there are two middle nodes, return the second middle node.

英文版地址

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

中文版描述

给定一个头结点为 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 之间

中文版地址

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

解题思路

由于无法直接获取到链表的长度，所以我们需要先从链表头遍历到链表尾，获取到链表的长度，然后找到他的中间节点。

解题方法

俺这版

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        int len = 0;
       ListNode myHead = head;
        while (myHead != null) {
            len++;
            myHead = myHead.next;
        }
        int index = len / 2;
        for (int i = 1; i <= index; i++) {
            head = head.next;
        }
        return head;
    }
}

复杂度分析

• 时间复杂度：O(n)

• 空间复杂度：O(1)，常数空间

官方版

官方提供了三种方法

数组

这个方法就是空间换时间的感觉

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode[] A = new ListNode[100];
        int t = 0;
        while (head != null) {
            A[t++] = head;
            head = head.next;
        }
        return A[t / 2];
    }
}

复杂度分析

• 时间复杂度：O(N)，其中 N 是给定链表中的结点数目。

• 空间复杂度：O(N)，即数组 A 用去的空间。

单指针法

class Solution {
    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;
    }
}

复杂度分析

• 时间复杂度：O(N)，其中 NN 是给定链表的结点数目。

• 空间复杂度：O(1)，只需要常数空间存放变量和指针。

快慢指针法

思路和算法

我们可以继续优化方法二，用两个指针 slow 与 fast 一起遍历链表。 slow 一次走一步，fast 一次走两步 那么当 fast 到达链表的末尾时，slow 必然位于中间

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

复杂度分析

• 时间复杂度：O(N)，其中 N 是给定链表的结点数目。

• 空间复杂度：O(1)，只需要常数空间存放 slow 和 fast 两个指针。

总结

在解题思路中提到的方法是我最直接的解题思路（就是官方的单指针法），后面也有考虑要不要优化下，比如：自定一个数组，每便利一个节点，把该点的值存到对应位置的数组中，结束后，无需再次遍历链表，直接从数组中获取呀对应序号的值即可（也就是官方的数组法），但感觉这个方法相比较单指针法其实也就是空间换时间，在空间比较珍贵的情况下，反而不见得能称为“优化”。 快慢指针，，绝了！！！