题目描述

[EN | CN]

给定一个链表,两两交换其中相邻的结点,并返回交换后的链表。

你不能只是单纯的改变结点内部的值,而是需要实际的进行结点交换。

示例:

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

解法 1:迭代

直接用迭代求解。

假设链表长度为 $n$,那么

  • 时间复杂度为 $O(n)$,遍历每个结点;
  • 空间复杂度为 $O(1)$,常数空间代价。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        pre = curr = ListNode(-1)
        pre.next = head

        while curr.next and curr.next.next:
            next1, next2, next3 = curr.next, curr.next.next, curr.next.next.next
            curr.next = next2
            next2.next = next1
            next1.next = next3
            curr = next1

        return pre.next
  • 执行用时:36 ms,在所有 Python3 提交中击败了 79.38% 的用户。
  • 内存消耗:13.4 MB,在所有 Python3 提交中击败了 6.25% 的用户。

解法 2:递归

递归的写法更简洁。

假设链表长度为 $n$,那么

  • 时间复杂度为 $O(n)$,遍历每个结点;
  • 空间复杂度为 $O(n)$,空间代价与递归深度有关,而空间代价与链表长度成正比。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        tmp = head.next
        head.next = self.swapPairs(head.next.next)
        tmp.next = head
        return tmp
  • 执行用时:32 ms,在所有 Python3 提交中击败了90.80% 的用户。
  • 内存消耗:13.5 MB,在所有 Python3 提交中击败了6.25% 的用户。