Friday, November 7, 2014

Facebook: Interweave a linked list

Interweave a linked list. Do it in linear time and constant space.

Input: A->B->C->D->E
Output: A->E->B->D->C

Leetcode: Reorder the list
http://buttercola.blogspot.com/2014/08/leetcode-reorder-list.html

Code (Java):
public class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        
        // Find middle point of the list
        ListNode mid = findMiddle(head);
        
        ListNode newHead = mid.next;
        mid.next = null;
        
        // Reverse the second list
        newHead = reverseList(newHead);
        
        ListNode p = head;
        ListNode q = newHead;
        
        ListNode dummyNode = new ListNode(0);
        ListNode m = dummyNode;
        
        while(p != null && q != null) {
            m.next = p;
            p = p.next;
            m = m.next;
            
            m.next = q;
            q = q.next;
            m = m.next;    
        }
        
        if (p != null) {
            m.next = p;
        } else {
            m.next = q;
        }
        
        return dummyNode.next;
    }
    
    private ListNode findMiddle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return slow;
    }
    
    private reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        
        while (curr != null) {
            ListNode next = curr.next;
            
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        return prev;
    }
}

No comments:

Post a Comment