Problem

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

Example:

Given 1->2->3->4, you should return the list as 2->1->4->3.

Note:

Your algorithm should use only constant extra space.
You may not modify the values in the list’s nodes, only nodes itself may be changed.

Solution

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

class Solution {

public:

ListNode *swapPairs(ListNode *head) {

if (!head || !head->next) return head;

ListNode d(0);

d.next = head;

head = &d;

while (head && head->next && head->next->next) {

auto n1 = head->next;

auto n2 = n1->next;

n1->next = n2->next;

n2->next = n1;

head->next = n2;

head = n1;

}

return d.next;

}

};

class Solution:

def swapPairs(self, head):

if not head or not head.next: return head

dummy = ListNode(0)

dummy.next = head

head = dummy

while head.next and head.next.next:

n1, n2 = head.next, head.next.next

n1.next = n2.next

n2.next = n1

head.next = n2

head = n1

return dummy.next