Leetcode 24 Swap Nodes in Pairs

发表于 |

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

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

说明:
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

思路分析：
题目要求我们使用常数的额外空间，意思是不让我们用递归。迭代就稍微麻烦一点，但思路一样，我们先看递归怎么写，然后推出迭代怎么写。

递归：

1
2
3
4
5
6
7
8
class Solution(object):
    def swapPairs(self, head):
        if not head or not head.next: return head
        cur = head.next
        pre = head
        nex = cur.next
        cur.next,pre.next = pre, self.swapPairs(nex)
        return cur

那么迭代就很好想了，我们只需要将pre.next就指向nex.next，然后把pre,cur换成nex,nex.next即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 20ms, beats 100%
class Solution(object):
    def swapPairs(self, head):
        if not head or not head.next: return head
        ret = ListNode(0)
        ret.next = head.next # 指向最后的头结点

        pre, cur = head, head.next
        while cur:
            nex = cur.next
            cur.next = pre
            if nex and nex.next:
                pre.next = nex.next
            else: # 处理一下边界情况
                pre.next = nex
                break
            pre, cur = nex, nex.next
        return ret.next