Java Iterative solution using constant space and good explanation.


  • 2
    S

    I have made use of 'newHead', 'first', 'prev' and 'second' pointers. 'newHead' is the dummy head. 'prev' pointer is always one node before 'first' before swapping. 'second' is one node ahead of 'first'. And 'first' is one node ahead of 'newHead' in the start. Look at the explanation below.

    before first iteration: -

    newHead  first    second      
    |          |       |
    0          1       2       3  4
    |
    prev
    

    after first iteration: - doing the following changes yields: -

    prev.next = second;
    first.next = second.next;
    second.next = first;
    first = first.next;
    
    newHead     prev   first   second      
    |            |      |       |
    0        2   1      3       4
    

    The complete code is as below.

    public class Solution {
        public ListNode swapPairs(ListNode head) {
    		if(head == null || head.next == null) {
    			return head;
    		}
    
    		ListNode newHead = new ListNode(0);
    		newHead.next = head;
    		ListNode first = head;
    		ListNode second = head.next;
    		ListNode prev = newHead;
    
    		while(second != null) {
    			prev.next = second;
    			first.next = second.next;
    			second.next = first;
    			first = first.next;
    			if(first != null && first.next != null) {
    				second = first.next;
    			}
    			else {
    				second = null;
    			}
    			prev = prev.next.next;
    		}
    		return newHead.next;
    	}
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.