24. Swap Nodes in Pairs

Leetcode Linked List

题目

Given 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.

中文题目

将链表中相邻的两个节点交换位置，注意第一个节点与第二个节点要交换位置，而第二个节点不用与第三个节点交换位置。

例子： 输入: head = 1->2->3->4 输出: 2->1->4->3

不允许修改节点的值, 且只能用常量的额外空间

思路

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        newhead = ListNode(0)
        newhead.next = head
        results = newhead
        while newhead.next and newhead.next.next:

            before = newhead
            first = newhead.next
            second = first.next
            after = second.next

            before.next = second
            second.next = first
            first.next = after

            newhead = newhead.next.next

        return results.next