24.md

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.

Thinking Process

1. Create a dummy node that points to either head or head.next depending on how if there're more than 1 item in the list.
2. Keep track of the 4 nodes, left, right, nextLeft, nextRight. Update them according as we traverse through the list

Code

public class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null){
            return null;
        }
      	//determine the head of the returned list
        ListNode dummy = new ListNode(0);
        dummy.next = (head.next == null) ? head : head.next;
        ListNode left = head;
        ListNode right = head.next;
        
     	//swap left and right, find the next pair of left and right
        while(left != null && right != null){
            ListNode nextLeft = right.next;
            ListNode nextRight = (nextLeft == null) ? null : nextLeft.next;
            right.next = left;
            left.next = (nextRight != null) ? nextRight : nextLeft;
            left = nextLeft;
            right = nextRight;
        }
        return dummy.next;
    }
}

Complexity

1. Space complexity is O(1) since the program only uses constant space
2. Time complexity is O(n) since the list is traversed exactly once