Wednesday, September 3, 2014

Leetcode: 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.
Understand the problem:
The problem gives a linked list, swap every two adjacent nodes and return its head. For e.g. For 1->2->3->4, swap 1 and 2, 3 and 4, return 2->1->4->3. There are two requirements in the problem: you could only use constant space. You cannot modify the value in the list, just change the nodes. 

Let's take several examples to show the problem.
For a single node list, 1, return 1
For 1->2, return 2->1
For 1->2->3, return 2->1->3.
For 1->2->3->4->5, return 2->1->4->3->5

Solution:
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        
        ListNode helper = new ListNode(0);
        helper.next = head;
        
        ListNode pre = helper;
        ListNode p = null;
        ListNode q = null;
        ListNode post = head;
        
        while (post != null) {
            p = post;
            q = post.next;
            if (q == null) break;
            
            post = post.next.next;
            pre.next = q;
            q.next = p;
            p.next = post;
            
            pre = p;
        }
        
        return helper.next;
    }
}


A Neat Solution:
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        
        ListNode helper = new ListNode(0);
        helper.next = head;
        
        ListNode pre = helper;
        ListNode cur = pre.next;
        
        while (cur != null && cur.next != null) {
            pre.next = cur.next;
            cur.next = cur.next.next;
            pre.next.next = cur;
            
            pre = cur;
            cur = pre.next;
        }
        
        return helper.next;
    }
}

Update on 9/21/15:
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        
        ListNode prev = dummyNode;
        ListNode curr = head;
        
        int count = 0;
        
        while (curr != null) {
            count++;
            if (count % 2 == 1) {
                curr = curr.next;
            } else {
                ListNode next = curr.next;
                curr.next = prev.next;
                prev.next.next = next;
                prev.next = curr;
                
                prev = curr.next;
                curr = next;
            }
        }
        
        return dummyNode.next;
    }
}


No comments:

Post a Comment