876. Middle of the Linked List
该题目给定一个链表，找出链表中间的那个节点，如果是偶数的话，返回中间后边的节点
1
2
3
4
5
| Input: [1,2,3,4,5]
Output: [3,4,5]
Input: [1,2,3,4,5,6]
Output: [4,5,6]
|
常规解法
遍历这个链表，然后把每一个节点放在数组里边，取数组的中间值，返回。go 语言实现如下
1
2
3
4
5
6
7
8
9
10
11
12
| func middleNode(head *ListNode) *ListNode {
array := make([]*ListNode, 0)
for {
if head != nil {
array = append(array, head)
head = head.Next
} else {
break
}
}
return array[len(array) / 2]
}
|
Time Complexity: O(N)
Space Complexity: O(N)
快慢指针
一个走一步，一个走两步，当走两步的到达末尾的时候，走一步的那个，就正好在中间。go 语言实现如下
1
2
3
4
5
6
7
8
| func middleNode(head *ListNode) *ListNode {
var slow,fast = head,head
for fast != nil && fast.Next!=nil{
slow = slow.Next
fast = fast.Next.Next
}
return slow
}
|
Time Complexity: O(N)
Space Complexity: O(1)
顺便吐槽一下 LeetCode 的代码运行机制，如第一种方式，如果把 array 方在函数体外边，直接 Run Code 是没问题的，但是当 Submit 的时候，就会报错，提示 Wrong Answer。这个错误搞得我都要怀疑人生了，后来突然灵光一现，发现，只要把变量放在函数里边就 OK 了，也是醉了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| ,--^----------,--------,-----,-------^--,
| ||||||||| `--------' | O
`+---------------------------^----------|
`\_,-------, _________________________|
/ XXXXXX /`| /
/ XXXXXX / `\ /
/ XXXXXX /\______(
/ XXXXXX /
/ XXXXXX /
(________(
,--^----------,--------,-----,-------^--,
| ||||||||| `--------' | O
`+---------------------------^----------|
`\_,-------, _________________________|
/ XXXXXX /`| /
/ XXXXXX / `\ /
/ XXXXXX /\______(
/ XXXXXX /
/ XXXXXX /
(________(
`------'
|