LeetCode 24. 两两交换链表中的节点（中）

基本的链表问题

题目

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例

1
给定 1->2->3->4, 你应该返回 2->1->4->3.

考察知识点

链表

核心思想

一、递归

从链表的头节点 head 开始递归。 每次递归都负责交换一对节点。由 firstNode 和 secondNode 表示要交换的两个节点。 下一次递归则是传递的是下一对需要交换的节点。若链表中还有节点，则继续递归。 交换了两个节点以后，返回 secondNode，因为它是交换后的新头。 在所有节点交换完成以后，我们返回交换后的头，实际上是原始链表的第二个节点

二、迭代

我们把链表分为两部分，即奇数节点为一部分，偶数节点为一部分，A 指的是交换节点中的前面的节点，B 指的是要交换节点中的后面的节点。在完成它们的交换，我们还得用 prevNode 记录 A 的前驱节点。

LeetCode题解

关键是熟悉链表的结构，和如何替换，实际上就两个步骤。下面两行代码，十分重要。

1
2
first_node.next = second_node.next  # 将原来second_node后面的third_node接到first_node之后
second_node.next = first_node  # 将原来first_node接到second_node后面

Python版本

递归版本实现

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
class ListNode():
    def __init__(self, value):
        self.val = value
        self.next = None

    def __str__(self):
        return str(self.val)


def createList(value_list: list) -> ListNode:
    """
    Create Linked List based on list
    :param value_list: list
    :return: NodeList
    """
    _len = len(value_list)
    if _len == 0:
        return None
    if _len == 1:
        return ListNode(value_list[0])
    else:
        root = ListNode(value_list[0])
        tmp = root
        for i in range(1, _len):
            tmp.next = ListNode(value_list[i])  # 声明当前节点，再把当前节点与前面节点联系在一起。
            tmp = tmp.next  # 更新tmp
    return root # 返回根节点


def listLength(head: ListNode) -> int:
    """
    Get the length of linked list
    :param head: ListNode
    :return: int
    """
    count = 0
    p = head
    while p != None:
        count += 1
        p = p.next
    return count


def convert2list(head: ListNode) -> list:
    """
    Convert linked list to normal list
    :param head: ListNonde
    :return: list
    """
    res = []
    p = head
    while p != None:
        res.append(p.val)  # 由于有ListNode实现了__str__函数 就不用调用p.val来获取节点值了
        p = p.next
    return res


class Solution(object):
    def swapPairs(self, head: ListNode) -> ListNode:
        """
        :type head: ListNode
        :rtype: ListNode
        """

        # If the list has no node or has only one node left.
        if not head or not head.next:  # 一直交换，直到head为None。
            return head

        # Nodes to be swapped
        first_node = head  # 选定当前节点为first_node
        second_node = head.next

        # Swapping
        # 开始之前：first_node -> second_node -> third_node
        first_node.next  = self.swapPairs(second_node.next)  # 下一次递归，传递的是下一对需要交换的节点的前一个节点，即second_node.next（third_node），且这个third_node节点要接到第一个节点first_node后面。
        # 现在：first_node -> third_node 且 second_node -> third_node
        second_node.next = first_node  # 将前一个节点放到后一个节点之后，完成交换。
        # 最后：second_node -> first_node -> third_node 完成交换

        # Now the head is the second node
        return second_node

    
print("leet code accept!!!")
Input = [[1, 2, 3, 4]]
Answer = [[2, 1, 4, 3]]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        result = solution.swapPairs(createList(Input[i]))
        print(convert2list(result))
        print(Answer[i])

时间复杂度：\(O(N)\)，其中 N 指的是链表的节点数量。
空间复杂度：\(O(N)\)，递归过程使用的堆栈空间。
执行用时：在所有 Python3 提交中击败了11.14% 的用户。
内存消耗：在所有 Python3 提交中击败了38.68% 的用户。

迭代方法实现

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
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        # Dummy node acts as the prevNode for the head node
        # of the list and hence stores pointer to the head node.
        dummy = ListNode(-1)  # 声明哑节点
        dummy.next = head  # 哑结点与head互联

        prev_node = dummy  # prev_node永远在first_node前面，用 prevNode 记录first节点的前驱。相当于一个跟踪标记，将所有递归和dummy串联起来。

        while head and head.next:

            # Nodes to be swapped
            first_node = head
            second_node = head.next

            # Swapping
            prev_node.next = second_node  # 将原来first_node的位置替换成second_node
            first_node.next = second_node.next  # 将原来second_node后面的third_node接到first_node之后
            second_node.next = first_node  # 将原来first_node接到second_node后面

            # Reinitializing the head and prev_node for next swap
            prev_node = first_node  # prev_node永远在等待替换的first_node前面
            head = first_node.next  # 更新third_node为新的head

        # Return the new head node.
        return dummy.next

时间复杂度：\(O(N)\)，其中 N 指的是链表的节点数量。
空间复杂度：\(O(1)\)。
执行用时 :32 ms, 在所有 Python3 提交中击败了78.62%的用户
内存消耗 :13.5 MB, 在所有 Python3 提交中击败了38.68%的用户
这个用时和内存排名，十分不准确。