数据结构与算法 | Leetcode 876. middle-of-the-linked-list

前面,我们实现了 删除单链表倒数第N个节点 操作,本篇来聊聊,如何求一个链表的中间节点。

求链表的中间结点

Leetcode 876. Middle of the Linked List

给定一个非空的单链表,要求返回它的中间节点,如果中间节点有两个则返回第二个。

例如:

1
2
Input: [1,2,3,4,5]
Output: Node 3 from this list
1
2
Input: [1,2,3,4,5,6]
Output: Node 4 from this list

解法一

第一种解法的思路比较容易想得到,先计算出链表的总长度,再计算出中间节点的下标,然后得遍历得到对应的节点即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
if(head == null){
return null;
}
int len = 0;
for(ListNode curr = head; curr != null; ){
len++;
curr = curr.next;
}
int targetIndex = 0;
ListNode target = null;
for(ListNode curr = head; curr != null; ){
if(targetIndex == len / 2){
target = curr;
break;
}
targetIndex++;
curr = curr.next;
}
return target;
}
}

解法二

第二种解法,使用快慢指针,让快指针的移动速度是慢指针的两倍,等到快指针到达终点时,慢指针恰好抵达中间节点。

一段小路上,A车行驶的速度是B车的两倍,等到A车到达终点时,B车恰好达到小路的中间位置。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {

public ListNode middleNode(ListNode head) {
if(head == null){
return null;
}

ListNode slow = head;
ListNode fast = head;

for(ListNode curr = slow; slow != null; ){
if(fast == null || fast.next == null){
break;
}else{
fast = fast.next.next;
}
slow = slow.next;
}
return slow;
}
}

到目前为止,我们已经使用快慢指针解决三个单链表相关的问题了:

单链表环检测

删除单链表倒数第N个节点

求链表的中间结点

解法三

解法三也比较巧妙, 遍历单链表,只有当下标为奇数时,指针才向前移动,到最后,指针所指即为中间节点。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {

public ListNode middleNode(ListNode head) {
if(head == null){
return null;
}
ListNode target = head;
int index = 0;
for(ListNode curr = head; curr != null; ){
if(index % 2 == 1){
target = target.next;
}
index++;
curr = curr.next;
}
return target;
}
}

以上三种解法的时间复杂度均为O(n),在leetcode上的运行时间为 1ms,超过 82.96%

相关练习

参考资料

请我喝半杯☕️