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


https://leetcode.com/problems/swap-nodes-in-pairs

Consider example 1->2->3->4->5 rotate the list by 2. 3->4->1->2->5.

Since the question is simple enough to understand, we can directly jump to the solution.

The LinkedList for the example is singly. Here is how Node class looks like:

class ListNode {
	int value;
	protected ListNode next;
	
	public ListNode(int value) {
		this.value = value;
	}	
}

Method 1. Recursive

public class RotateLinkedList {

	public ListNode swapPairs(ListNode head) {
		if (head == null)
			return head;
		ListNode temp = null;
		ListNode future = null;
		if(head.next != null) {
			 temp = head.next;
			 future = temp.next;
			 temp.next = head;
		} else {
			return head;
		}
		head.next = swapPairs(future);
		return temp;
	}

    public static void main(String[] args) {
		ListNode l = new ListNode(1);
		ListNode l1 = new ListNode(2);
		ListNode l2 = new ListNode(3);
		ListNode l3 = new ListNode(4);
		ListNode l4 = new ListNode(5);
		l.next = l1;l1.next=l2;l2.next=l3;l3.next=l4;
		System.out.println("Original List");
		ListNode n = l;
		while(n != null) {
			System.out.print(n.val +" ");
			n=n.next;
		}
		System.out.println("");
		//reverse by k
		n = new RotateLinkedList().swapPairs(l);
		System.out.println("New List: ");
		while(n != null) {
			System.out.print(n.val +" ");
			n=n.next;
		}
	}
}

Output:
Original List
1 2 3 4 5 
New List: 
4 3 2 1 5	

Method 2. Iterative method

public class RotateLinkedList {

	public ListNode swapPairs(ListNode head) {
	    ListNode dummy = new ListNode(0);
	    dummy.next = head;
	    ListNode current = dummy;
	    while (current.next != null && current.next.next != null) {
	        ListNode first = current.next;
	        ListNode second = current.next.next;
	        first.next = second.next;
	        current.next = second;
	        current.next.next = first;
	        current = current.next.next;
	    }
	    return dummy.next;
	}
    public static void main(String[] args) {
		ListNode l = new ListNode(1);
		ListNode l1 = new ListNode(2);
		ListNode l2 = new ListNode(3);
		ListNode l3 = new ListNode(4);
		ListNode l4 = new ListNode(5);
		l.next = l1;l1.next=l2;l2.next=l3;l3.next=l4;
		System.out.println("Original List");
		ListNode n = l;
		while(n != null) {
			System.out.print(n.val +" ");
			n=n.next;
		}
		System.out.println("");
		//reverse by 2
		n = new RotateLinkedList().swapPairs(l);
		System.out.println("New List: ");
		while(n != null) {
			System.out.print(n.val +" ");
			n=n.next;
		}
	}
}

Output:
Original List
1 2 3 4 5 
New List: 
4 3 2 1 5	

Subscribe to get latest updates.

© 2016 Java Questions | Sitemap