Swap Nodes in Pairs

Problem: Swap Nodes in Pairs

Everytime we swap two nodes, we need to know the node leading them, and the node following them, then we can do the swapping. Besides, we also need to consider corner cases when there are odd number of pairs.

Code in Python:

# 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
        ans, node, prev = head.next, head, None
        while node and node.next:
            if prev: prev.next = node.next
            tmp = node.next
            node.next, tmp.next = tmp.next, node
            node, prev = node.next, node
        return ans

Code in Java:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode n1 = head, n2 = head.next;
        ListNode res = new ListNode(0);
        ListNode rear = res;

        while (n1 != null && n2 != null) {
            rear.next = n2;
            rear = rear.next;
            ListNode tmp = n2.next;
            rear.next = n1;
            rear = rear.next;

            n1 = tmp;
            if (n1 != null)
                n2 = n1.next;
        }

        if (n1 != null) {
            rear.next = n1;
            rear = rear.next;
        }

        rear.next = null;
        return res.next;
    }
}