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.

Solution

(1) Java

/**
 * 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 prev = dummy;
        ListNode p1 = head;
        while (p1 != null && p1.next != null) {
            ListNode p2 = p1.next;
            ListNode p3 = p2.next;
            prev.next = p2;
            p2.next = p1;
            p1.next = p3;
            prev = p1;
            p1 = p3;
        }
        return dummy.next;
    }
}

(2) 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
        """
        dummy,prev, prev.next, p1 = self, self, head, head
        while p1 and p1.next:
            p2 = p1.next
            p3 = p2.next
            prev.next, p2.next, p1.next = p2, p1, p3
            prev, p1 = p1, p3
        return dummy.next

(3) Scala

/**
 * Definition for singly-linked list.
 * class ListNode(var _x: Int = 0) {
 *   var next: ListNode = null
 *   var x: Int = _x
 * }
 */
object Solution {
    def swapPairs(head: ListNode): ListNode = {
        val dummy = ListNode(0)
        dummy.next = head
        var prev = dummy
        var p1 = head
        while (p1 != null && p1.next != null) {
            var p2 = p1.next
            var p3 = p2.next
            prev.next = p2
            p2.next = p1
            p1.next = p3
            prev = p1
            p1 = p3
        }
        return dummy.next
    }
}