反转链表及其变体

发表于 分类于
本文字数： 3.6k 阅读时长 ≈ 3 分钟

本文记录反转链表的几个典型例题，从迭代和递归的两种方法解决以下几个问题：

206. 反转链表

题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

1、迭代解法：

1
2
3
4
tmp := cur.Next		// 暂存 cur 的 next 节点
cur.Next = pre		// 将 pre 节点赋值给 cur.Next
pre = cur			// pre向后移动一步
cur = tmp			// cur向后移动一步

可以把上面的步骤合并成一句，完整代码如下：

1
2
3
4
5
6
7
8
func reverseList(head *ListNode) *ListNode {
    var pre *ListNode
    cur := head
    for cur != nil {
        pre, cur, cur.Next = cur, cur.Next, pre
    }
    return pre
}

定义 pre 节点的时候，用 var 关键字声明并初始化为零值，即 nil。如果用短变量声明操作符 := 做不到将 pre 设置为 nil。

2、递归解法

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

递归解法的时间复杂度与迭代解法一样都是O(N)，但是递归使用的栈空间大小是 O(N)，而迭代解法是 O(1)。但是递归解法思路很清晰，就是将一个大的问题化解为一个更小一点的问题，直到临界情况下直接返回结果即可，这对后续题目的解决提供了一种思路。

反转链表前N个节点

题目：将链表的前 n 个节点反转（n <= 链表长度）

1、迭代解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func reverseN(head *ListNode, n int) *ListNode {
    preHead := &ListNode{
        Next: head,
    }
    var pre *ListNode
    cur := head
    i := 0
    for i < n {
        pre, cur, cur.Next = cur, cur.Next, pre
        i++
    }
    preHead.Next.Next = cur
    return pre
}

2、递归解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func reverseN(head *ListNode, n int) *ListNode {
    var successor  *ListNode	// 用于记录第n个节点的next节点 
    
    var helper func(head *ListNode, n int) *ListNode
    helper = func(head *ListNode, n int) *ListNode {
        if n == 1 {
            successor = head.Next
            return head
        }
        last := helper(head.Next, n-1)
        head.Next.Next = head
        head.Next = successor
        return last
    }
    
    return helper(head, n)
}
92. 反转链表 II

题目：给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表。

1、迭代解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func reverseBetween(head *ListNode, left int, right int) *ListNode {
    preHead := &ListNode{
        Next: head,
    }
    pre, cur, next := preHead, head, head.Next
    i := 1
    for {
        if i < left {
            pre, cur, next = cur, next, next.Next
        } else if i >= left && i < right {
            cur, next, next.Next = next, next.Next, cur
        } else {
            pre.Next.Next = next	// 当超过范围之后，将pre.Next节点next节点指向next
            pre.Next = cur			// pre节点的next指向指向cur
            break
        }
        i++
    }

    return preHead.Next
}

2、递归解法

当left = 1时，利用reverseN的思路求解。

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
func reverseBetween(head *ListNode, left int, right int) *ListNode {
    if left == 1 {
        return reverseN(head, right)
    }

    head.Next = reverseBetween(head.Next, left-1, right-1)
    return head
}

func reverseN(head *ListNode, n int) *ListNode {
    var successor  *ListNode	// 用于记录第n个节点的next节点 
    
    var helper func(head *ListNode, n int) *ListNode
    helper = func(head *ListNode, n int) *ListNode {
        if n == 1 {
            successor = head.Next
            return head
        }
        last := helper(head.Next, n-1)
        head.Next.Next = head
        head.Next = successor
        return last
    }
    
    return helper(head, n)
}
25. K 个一组翻转链表

题目：给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

1、迭代解法

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
func reverseKGroup(head *ListNode, k int) *ListNode {
    preHead := &ListNode{Next: head}
    pre := preHead
    for head != nil {
        tail := pre
        for i := 0; i < k; i++ {
            tail = tail.Next
            if tail == nil {
                return preHead.Next
            }
        }
        next := tail.Next
        head, tail = reverse(head, tail)
        pre.Next = head
        tail.Next = next
        pre = tail
        head = tail.Next
    }
    
    return preHead.Next
}

func reverse(head, tail *ListNode) (*ListNode, *ListNode) {
    pre := tail.Next
    cur := head
    for pre != tail {
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
    return tail, head
}

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
func reverseKGroup(head *ListNode, k int) *ListNode {
    if k == 1 {
        return head
    }

    a, b := head, head
    for i := 0; i < k; i++ {
        if b == nil {
            return head
        }
        b = b.Next
    }

    newHead := reverse(a, b)
    a.Next = reverseKGroup(b, k)
    return newHead
}

// 反转[a, b)的节点，当b=nil时，即反转整个链表
func reverse(a, b *ListNode) *ListNode {
    var pre *ListNode
    cur := a
    for cur != b {
        pre, cur, cur.Next = cur, cur.Next, pre
    }
    return pre
}