24. Swap Nodes in Pairs

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.

Thoughts:

1. Recusively solve the problem, but O(n) extra space

2. Iteratively: Here,preis the previous node. Since the head doesn't have a previous node, I just useselfinstead. Again,ais the current node andbis the next node. To go frompre -> a -> b -> b.nexttopre -> b -> a -> b.next, we need to change those three references. Instead of thinking about in what order I change them, I just change all three at once.(StefanPochmann's post)

Code: Recursively swaping every pairs

# 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
        """
        if not head or not head.next: return head
        n = head.next
        head.next = self.swapPairs(head.next.next)
        n.next = head

        return n

Code: Iteratively

# 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):
        dummy = ListNode(0)
        pre, pre.next = dummy, head
        while pre.next and pre.next.next:
            a = pre.next
            b = pre.next.next
            pre.next, b.next, a.next = b, a, b.next
            pre = a
        return dummy.next

Code: Iteratively

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
        while (cur.next != null && cur.next.next != null) {
            ListNode first = cur.next;
            ListNode second = cur.next.next;
            first.next = second.next;
            cur.next = second;
            cur.next.next = first;
            cur = cur.next.next;
        }
        return dummy.next;
    }
}