Leetcode(24) Swap Nodes in Pairs

发表于 | 更新于 | 分类于

Description:

iven a linked list, swap every two adjacent nodes and return its head.

For example, Given 1->2->3->4, you should return the list as 2->1->4->3. Your algorithm should use only constant space.

You may not modify the values in the list, only nodes itself can be changed.

解法：

需要建立dummy节点，（即头指针前的虚拟节点），注意在连接节点的时候，最好画个图，以免把自己搞晕了，代码如下：

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

class Solution:
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if(head == None):
            return None;
        dummy = ListNode(-1);
        pre = dummy;
        dummy.next = head;
        while(pre.next and pre.next.next):
            tmp = pre.next;
            pre.next = tmp.next;
            tmp.next = pre.next.next;
            pre.next.next = tmp;
            pre = tmp;
        return dummy.next;