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

太过爱你忘了你带给我的痛 2024-04-06 14:08 62阅读 0赞

## 题目描述 ##

### 英文版描述 ###

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/

## 解题思路 ##

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

## 解题方法 ##

### 俺这版 ###

![dea6d465e256488fd1e969eb49b93fc5.png][]

/**
     * 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)，常数空间

### 官方版 ###

官方提供了三种方法

#### 数组 ####

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

![6e8e6e7d5032b5a25cd6c96e424cb74b.png][]

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 用去的空间。

#### 单指针法 ####

![ce3561f2e13123629c30abbc69227b8a.png][]

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 必然位于中间

![ed7c4357161619e0ae2443f107f5ebd6.png][]

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 两个指针。

## 总结 ##

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

[dea6d465e256488fd1e969eb49b93fc5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/5836a93760994665acae409ef67d5409.png
[6e8e6e7d5032b5a25cd6c96e424cb74b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/1dd8099ae2ea470a8dad59b763638c00.png
[ce3561f2e13123629c30abbc69227b8a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/cd67430d999c46e2a73d119a83a90736.png
[ed7c4357161619e0ae2443f107f5ebd6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/ca2323c1ecf84d09821a6c37ea5bbcf1.png