Interview Question Swap Nodes in Pairs

By Fatih KABAKCI

The problem is to swap each consecutive two nodes and return the same linked list.

Problem #24 - Swap Nodes in Pairs

Description: 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.

Difficulty: Easy

Solution in Java

head: {1		2		3	 	4}
root -> 1 2 3 4
r = root -> 1 2 3 4

while(r-next != null and r->next->next != null)
START CYCLE 0
	n = r->next;
		Then n : {1 2 3 4}, r -> {1 2 3 4}, root -> {1 2 3 4}
	p = r->next->next;
		Then p : {2 3 4}, r -> {1 2 3 4}, root -> {1 2 3 4}
	n->next = p->next; 
		Then n : {1 3 4}, r -> {1 3 4}, root -> {1 3 4}
	p->next = n;
		Then p : {2 1 3 4}, r -> {1 3 4}, root -> {1 3 4}
	r->next = p;
		Then r -> {2 1 3 4}, root -> {2 1 3 4}
	r = r.next.next;
		Then r : {1 3 4}, root -> {2 1 3 4}
END CYCLE 0
START CYCLE 1
	n = r->next;
		Then n : {3 4}, r : {1 3 4}, root -> {2 1 3 4}
	p = r->next->next;
		Then p : {4}, r : {1 3 4}, root -> {2 1 3 4}
	n->next = p->next; 
		Then n : {3 null}, r : {1 3}, root -> {2 1 3 4}
	p->next = n;
		Then p : {4 3 null}, r : {1 3}, root -> {2 1 3 4}
	r->next = p;
		Then r : {1 4 3 null}, root -> {2 1 4 3}
	r = r.next.next;
		Then r : {3, null}
END CYCLE 1
end while

package com.fatihkabakci.Easy.SwapNodesinPairs;
/**
 * @author fkabakci
 * 
 * Problem Description: 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.
 * 
 * Solution:
 * 
 * When head is {1, 2, 3, 4}
 * 
 * 1. Define an empty node and then connect its next to the head.
 * 	  root -> {1, 2, 3, 4}
 * 
 * 2. Copy of root node.
 * 	  r -> {1, 2, 3, 4}
 * 
 * 3. Start with first two nodes. 
 * 	  r -> {1, 2, 3, 4}
 *              n  p
 * 4. Swap them.
 * 	  a. Connect next of p to next of n.
 *        b. Connect n to next of p.
 *        c. Connect p to next of r to keep r updated.
 * 
 * 5. Skip two nodes.
 */

public class SwapNodesinPairs {
	public ListNode swapPairs(ListNode head) {
		ListNode root = new ListNode(0);
		root.next = head;
	    ListNode r = root;
        while(r.next != null && r.next.next != null) {
			ListNode n = r.next;
			ListNode p = r.next.next;
			n.next = p.next;
			p.next = n;
			r.next = p;
			r = r.next.next;
        }
        return root.next;
    }
	
	public static void main(String[] args) {
		SwapNodesinPairs r = new SwapNodesinPairs();
		ListNode head = Data.init(new int[]{1, 2, 3, 4});
		ListNode entire = r.swapPairs(head);
		while(entire != null) {
			System.out.print(entire.val + " ->");
			entire = entire.next;
		}
	}
}

Similar Problems