Preface

单链表的反转，按K反转等各种考点变体。

处理单链表时， 尽量采用递归实现：

  • 1 因为递归代码简洁+优美，节省时间，并且不容易出错，是面试优选策略。
  • 2 在面试时间比较宝贵的情况下，尽量预留时间展示自己的才能。

1 反转单链表(基础)

单链表结构定义如下：

1
2
3
4
5

// Definition for singly-linked list.
type ListNode struct {
    Val  int
    Next *ListNode
}

方法一: 递归实现(尾插法)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// 尾插法
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    tail := reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil
    return tail // became new head
}

方法二: 循环实现(头插法)

双指针,头插法:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func reverseListIter(head *ListNode) *ListNode {
    var newHead *ListNode
    for head != nil {
        pop := head
        head = head.Next
        // 插入新链表头部
        pop.Next = newHead
        newHead = pop
    }
    return newHead // 原链表的尾元素
}

2 变体一： 递归实现-从 m 到 n 中间节点的反转

上面我们使用递归，实现了反转整个链表的算法； 稍微改造下，只反转前k个元素(即递归深度到第k个元素，就可以返回)。

递归实现(从head 开始, 只反转前k个元素): 输入： 1->2->3->4->5->6->7->8 反转前5个 输出：[5->4->3->2->1]->6->7->8

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

// reverseTopK 递归反转链表前k个节点
// 返回：反转后的头结点
func reverseTopK(head *ListNode, k int) *ListNode {
	// 边界
	if head == nil || k <= 1 {
		return head
	}
	newHead := reverseTopK(head.Next, k-1)
    // 调整当前节点指向
	adjust(head)
	return newHead
}

func adjust(cur *ListNode) {
    // 保存下下个节点（反转完成后要接上尾部剩余链表）
	nextNext := cur.Next.Next
	// 指针反转
	cur.Next.Next = cur
	// 切断
	cur.Next = nextNext
}

反转中间一部分[m,n], 再分析一下：
一种特殊情况是，m=1, 也就是反转前 n 个元素。
当 m = 2 ,我们把第一个节点去掉，就可以转化为上面的特殊情况了；
总结一下： 推广到一般的情况(m>1)，都可以转换为 m=1 的特殊情况处理。

1
2
3
4
5
6
7
8

// 反转中间一部分[m,n] 递归实现
func reverseBetween(head *ListNode, m, n int) *ListNode {
    if m == 1 {
        return reverseTopK(head, n)
    }
    head.Next = reverseBetween(head.Next, m-1, n-1)
    return head
}

3 变体二: 按K个元素一组反转 (最后一组不足K个不反转)

我们先考虑下特殊情况:
1 链表元素总个数n 小于 k, 不做反转直接返回即可。
2 如果等于k个, 那么把当前链表按k反转，并返回新的head节点。
3 如果多余k个，我们先按照情形2处理前k个元素，剩下的(n-k)的链表当成一个子问题，执行步骤1,2,3.

最后这个子问题解决后，返回它的头指针 tailHead，
我们再把当前块的尾指针 head.Next = tailHead 即可。

 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

func reverseKGroup(head *ListNode, k int) *ListNode {
    p := head
    for i := 0; i < k; i++ {
        // 不足k个直接返回
        if p == nil {
            return head
        }
        p = p.Next
    }
    newHead := reverseKCutTail(head, k)
    // 超过K个节点部分, 又是一个按K反转的问题
    head.Next = reverseKGroup(p, k)
    return newHead
}

// 反转链表前 K 个元素, 并截断尾部(注意与前文 reverseKKeepTail 的区别)
func reverseKCutTail(head *ListNode, k int) *ListNode {
    if k <= 1 {
        return head
    }
    rear := reverseKCutTail(head.Next, k-1)
    head.Next.Next = head
    head.Next = nil
    return rear
}

这个问题还有一个变体(从后往前分组), 这个题是 Shopee(2019年)的面试题：

解决办法：
1 先把整个链表全部反转，然后从新的head开始，按照k个一组，执行前插法；

注意：最后一个分组不足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
39
40
41
42
43
44
45
46
47

/* [逆序] 从后往前, 每k个反转一次(不足k个不反转)（循环实现）
输入：1->2->3->4->5->6->7  k = 3
输出: 1->4->3->2->7->6->5

输入：1->2->3->4->5->6->7->8  k = 3
输出: 1->2->5->4->3->8->7->6
*/

func reverse(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    last := reverse(head.Next)
    head.Next.Next = head
    head.Next = nil
    return last // became header
}

func reverseKGroup(head *ListNode, k int) *ListNode {
    rhead := reverse(head)
    count := 0
    cur := rhead
    remainList := rhead
    var newHead *ListNode
    for cur != nil {
        count++
        pre := cur
        cur = cur.Next
        if count == k {
            // 头插法
            pre.Next = newHead
            newHead = remainList
            // move next
            remainList = cur
            count = 0
        }
    }
    // 不足k个的部分,采用头插法
    for remainList != nil {
        pop := remainList
        remainList = remainList.Next
        // 头插法
        pop.Next = newHead
        newHead = pop
    }
    return newHead
}

总结

正所谓万变不离其宗，我们先分析问题的特殊场景，然后推广到一般；
把一般情况转化为一个个特殊场景的子问题，最后使用递归就可以完美解决。