Thursday, November 20, 2014

ReOrder List LeetCode

Good implementing question for LinkedList.

public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode reverseHead = slow.next;
        slow.next = null;
       
        reverseHead = reverse(reverseHead);
        ListNode curr = head;
        while (reverseHead != null) {
            ListNode temp = reverseHead.next;
            reverseHead.next = curr.next;
            curr.next = reverseHead;
            curr = reverseHead.next;
            reverseHead = temp;
        }
    }
   
    private ListNode reverse(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode prev = new ListNode(-1);
        prev.next = head;
        ListNode curr = head;
        while (curr.next != null) {
            ListNode temp = curr.next;
            curr.next = temp.next;
            temp.next = prev.next;
            prev.next = temp;
        }
        return prev.next;
    }

No comments:

Post a Comment