链表反转.md

链表是一个很简单的结构,虽然简单,但对于链表节点的操作,以及对于边界细节的处理,是面试中经常问到的。而且由于链表的定义符合递归定义,因此有时候考察递归思想时,也用链表来考察。

链表反转

给定一个单链表,写一个方法,将其反转,返回反转后的链表。
例如,给定一个链表 1->2->3->4->5 反转后 5->4->3->2->1

这是最基础的链表反转的题目,在leetcode上题目难度为简单。

对于链表的题目,可以使用递归思想,也可以使用迭代去解决。

递归

由于链表的定义就是递归的,因此链表的很多题目都可以使用递归。
使用递归的好处是,思考模型更直观,也更容易理解。

1
2
3
4
5
6
7
8
9
10
func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
next := head.Next
reversed := reverseList(next)
next.Next = head
head.Next = nil
return reversed
}

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
pre, current, next := head, head.Next, head.Next.Next
pre.Next = nil
for current != nil {
next = current.Next
current.Next = pre

pre = current
current = next
}

return pre
}

链表区间反转

给定一个链表,反转其从m到n这一区间的节点。只允许一次遍历。

例如,1->2->3->4->5,m=2,n=4 反转后,1->4->3->2->5

这个题目在leetcode上难度为中等。

比上面单纯的反转整个链表相比,难点在于,要反转的是链表的某个区间,所以这里要精确控制其边界。

这里我们使用迭代的方式,其思想就是,遍历链表,等遍历到区间m到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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
func reverseBetween(head *ListNode, m int, n int) *ListNode {
if head == nil || head.Next == nil {
return head
}
if m >= n {
return head
}
idx := 1
var pre, current, next *ListNode
var nodeM, mPre *ListNode

current = head

// 先找到第m个节点
for current != nil && idx < m {
pre = current
current = current.Next
idx++
}

nodeM = current
mPre = pre

pre = current
current = current.Next
next = current.Next
pre.Next = nil

// 开始反转区间链表
for current != nil && idx < n {
idx++
next = current.Next
current.Next = pre

pre = current
current = next
}

if mPre != nil {
mPre.Next = pre
} else {
head = pre
}
nodeM.Next = current

return head
}

链表间隔反转

给定一个链表,每2个节点为一组,进行反转。
例如,给定链表 1->2->3->4->5,反转后的链表为2->1->4->3->5

1
2
3
4
5
6
7
8
9
10
11
func reverse(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}

next := head.Next
head.Next = reverse(next.Next)
next.Next = head

return next
}

链表间隔k反转

给定一个链表,每k个节点一组,进行反转。
例如,给定链表 1->2->3->4->5->6->7,k=3,反转后链表为 3->2->1->6->5->4->7
这个题目是上面题目的一个延伸,上面是每2个节点为一组,这个题目是每k个节点,k是变量,由调用方决定。

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
32
33
34
35
36
37
38
func reverseK(head *ListNode, k int) *ListNode {
if head == nil || head.Next == nil {
return head
}

var pre, current, next *ListNode

count := 0
current = head
for current != nil {
count++
current = current.Next
if count == k {
break
}
}
// 如果链表长度小于k则不进行反转
if count < k {
return head
}

pre, current, next = head, head.Next, head.Next.Next
pre.Next = nil
idx := 2
for current != nil && idx <= k {
idx++
next = current.Next
current.Next = pre

pre = current
current = next
}

head.Next = reverseK(next, k)

return pre

}