Wednesday, July 16, 2014

Swap Nodes in Pairs

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.
public class Solution {
    //Time: O(n)  Space: O(1)
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        while (head.next != null && head.next.next != null) {
            ListNode temp = head.next.next;
            head.next.next = temp.next;
            temp.next = head.next;
            head.next = temp;
            head = head.next.next;
        }
        return dummy.next;
    }
}

No comments:

Post a Comment