文章目录
题目
标题和出处
标题：链表的中间结点
出处：876. 链表的中间结点
难度
3 级
题目描述
要求
给定一个头结点为 head \texttt{head} head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例
示例 1：
输入：
head
=
[1,2,3,4,5]
\texttt{head = [1,2,3,4,5]}
head = [1,2,3,4,5]
输出：
[3,4,5]
\texttt{[3,4,5]}
[3,4,5]
示例 2：
输入：
head
=
[1,2,3,4,5,6]
\texttt{head = [1,2,3,4,5,6]}
head = [1,2,3,4,5,6]
输出：
[4,5,6]
\texttt{[4,5,6]}
[4,5,6]
解释：由于该链表有两个中间结点，值分别为
3
\texttt{3}
3 和
4
\texttt{4}
4，我们返回第二个结点。
数据范围
- 链表中结点的数目在区间 [1, 100] \texttt{[1, 100]} [1, 100] 中
- 1 ≤ Node.val ≤ 100 \texttt{1} \le \texttt{Node.val} \le \texttt{100} 1≤Node.val≤100
解法一
思路和算法
由于链表的中间结点的编号和链表的结点数量相关，因此可以首先遍历链表得到链表的结点数量，然后计算链表的中间结点的编号，再定位到链表的中间结点。
假设链表的结点数量是 n n n，头结点到尾结点的编号依次是 1 1 1 到 n n n。当 n n n 分别是奇数和偶数时，链表的中间结点的编号如下：
-
当 n n n 是奇数时，链表有一个中间结点，其编号是 n + 1 2 = n − 1 2 + 1 \dfrac{n+1}{2}=\dfrac{n-1}{2}+1 2n+1=2n−1+1；
-
当 n n n 是偶数时，链表有两个中间结点，第二个中间结点的编号是 n 2 + 1 \dfrac{n}{2}+1 2n+1。
当 n n n 是偶数时， n n n 个结点的链表和 n + 1 n+1 n+1 个结点的链表的中间结点的编号相同。对任意正整数 n n n，中间结点的编号可以表示成 ⌊ n 2 ⌋ + 1 \Big\lfloor\dfrac{n}{2}\Big\rfloor+1 ⌊2n⌋+1。
因此在得到链表的结点数量 n n n 之后，从头结点开始，向后移动 ⌊ n 2 ⌋ \Big\lfloor\dfrac{n}{2}\Big\rfloor ⌊2n⌋ 次，即可定位到链表的中间结点。
代码
class Solution {
public ListNode middleNode(ListNode head) {
int n = 0;
ListNode temp = head;
while (temp != null) {
n++;
temp = temp.next;
}
int middleCount = n / 2 + 1;
ListNode middle = head;
for (int i = 1; i < middleCount; i++) {
middle = middle.next;
}
return middle;
}
}
复杂度分析
-
时间复杂度： O ( n ) O(n) O(n)，其中 n n n 是链表的长度。需要遍历链表一次得到链表的结点数量，然后遍历链表定位到链表的中间结点。
-
空间复杂度： O ( 1 ) O(1) O(1)。
解法二
思路和算法
得到链表的中间结点的另一种解法是快慢指针，使用快慢指针解法不需要事先知道链表的结点数量。
快慢指针的做法是：创建快指针和慢指针，初始时都指向头结点，然后每次将快指针往后移动 2 2 2 步，将慢指针往后移动 1 1 1 步，直到快指针到达链表的尾结点或者空结点（尾结点的后一个结点为空结点），此时慢指针指向的结点就是链表的中间结点。
证明
对于快慢指针解法的正确性证明，分别考虑链表的结点数量 n n n 是奇数和偶数的情况。
-
当 n n n 是奇数时，快指针会移动到链表的尾结点，一共移动 n − 1 n-1 n−1 步，慢指针移动 n − 1 2 \dfrac{n-1}{2} 2n−1 步，因此当移动结束时，慢指针位于第 n + 1 2 \dfrac{n+1}{2} 2n+1 个结点，是链表的中间结点。
-
当 n n n 是偶数时，快指针会移动到链表的空结点，一共移动 n n n 步，慢指针移动 n 2 \dfrac{n}{2} 2n 步，因此当移动结束时，慢指针位于第 n 2 + 1 \dfrac{n}{2}+1 2n+1 个结点，是链表的中间结点。
代码
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 ) O(n) O(n)，其中 n n n 是链表的长度。快指针遍历链表一次，慢指针遍历链表的前半段一次。
-
空间复杂度： O ( 1 ) O(1) O(1)。