【LeetCode 单链表专项】两两交换链表中的节点（24）_单向链表两两交换

文章目录

• • 1. 题目
  • • 1.1 示例
    • 1.2 说明
    • 1.3 限制
  • 2. 解法一（迭代）
  • • 2.1 分析
    • 2.2 解答
    • 2.3 复杂度
  • 3. 解法二（递归法）
  • • 3.1 分析
    • 3.2 解答
    • 3.3 复杂度

1. 题目

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

1.1 示例

• 示例 $1$ ：
  • 输入： head = [1, 2, 3, 4]
  • 输出： [2, 1, 4, 3]

• 示例 $2$ ：

  • 输入： head = []
  • 输出： []

• 示例 3$ ：

  • 输入： head = [1]
  • 输出： [1]

1.2 说明

• 来源： 力扣（LeetCode）
• 链接： https://leetcode-cn.com/problems/swap-nodes-in-pairs/

1.3 限制

• 链表中节点的数目在范围 [0, 100] 内
• 0 <= Node.val <= 100

2. 解法一（迭代）

2.1 分析

迭代法求解本题比较简单，只要注意以下三点即可：

1. 注意设置哑结点 dummy ，因为链表原来的头节点可能会在两两交换节点过程中被改变；
2. 使用 prev ，cur 和 succ 三个辅助变量，用于在两两交换节点时进行节点关系重新链接；
3. 注意循环终止条件是当前该对交换完成的节点之后无节点或仅有一个节点。

下面是迭代法求解的过程示意图：

2.2 解答

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, val: int):
        node = ListNode(val)
        if self.head is None:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = self.tail.next


class Solution:
    def swap_pairs(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        dummy = ListNode(-1, head)
        prev, cur, succ = dummy, head, head.next
        while True:
            prev.next = succ
            cur.next = succ.next
            succ.next = cur
            if not cur.next or not cur.next.next:
                break
            else:
                prev = cur
                cur = cur.next
                succ = cur.next
        return dummy.next


def main():
    values = [1, 2, 3, 4]
    lnk_lst = LinkedList()
    for val in values:
        lnk_lst.append(val)

    sln = Solution()
    head = sln.swap_pairs(lnk_lst.head)

    cursor = head
    while cursor:
        print(cursor.val, end='\t')  # 2	1	4	3
        cursor = cursor.next


if __name__ == '__main__':
    main()

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
48
49
50
51
52
53
54
55
56
57
58

2.3 复杂度

• 时间复杂度： $O(n)$ ；
• 空间复杂度： $O(1)$。

3. 解法二（递归法）

3.1 分析

使用递归解答题目的关键是明确当前这一层递归的操作需要做什么，而不要想一上来就尝试在大脑中将递归的所有层次就想象出来，毕竟之所以递归解法的空间复杂度一般而言较迭代解法高，原因在于在最深的递归返回之前，先前的递归状态都需要各种变量来维护，而你的大脑可没有这么多的存储空间。

实际上，站在当前这一层的角度来说，只需要假定除了前两个节点没有交换外，后续所有节点都已经完成了交换，而后续所有节点交换完成的结果使用递归函数 swap_pairs() 的返回结果来表示，其中函数参数为第三个节点。

基于上面的假设，问题就变成了三个节点之间的两两交换，这时问题就变得简单了，其交换的过程如下：

除此之外需要特别注意的两点是：

• 递归的出口是本层递归的头节点为 None 或仅有头节点；
• 递归的返回值应该是 succ 作为新的头节点。

3.2 解答

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
        

class Solution:
    def swap_pairs(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        succ = head.next
        head.next = self.swap_pairs(succ.next)
        succ.next = head
        return succ
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.3 复杂度

• 时间复杂度： $O(n)$ ；
• 空间复杂度： $O(n)$。