[Leetcode] Reorder List 鏈表重新排序

hufeng 發(fā)布于2019-08-14 12:40 / 559人閱讀

摘要：要找到后半部分的起點，就是用快慢指針。不過該題我們不能直接拿到中間，而是要拿到中間的前一個節(jié)點，這樣才能把第一個子鏈表的末尾置為空，這里的技巧就是快慢指針循環(huán)的條件是。注意因為不能有額外空間，我們最好用迭代的方法反轉(zhuǎn)鏈表。

Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes" values.

For example, Given {1,2,3,4}, reorder it to {1,4,2,3}

逆序合并法 復(fù)雜度

時間 O(N) 空間 O(1)

思路

理想情況下，如果能一個指針從后往前走，一個指針從前往后走，然后一個一個合并就行了。但是單鏈表并沒有從后往前走的能力，難道要改造成雙鏈表嗎？其實不用，我們只要把后半部分反轉(zhuǎn)一下，變成兩個鏈表就行了。要找到后半部分的起點，就是用快慢指針。從頭開始，快指針走兩步，慢指針走一步，這樣快指針到頭的時候慢指針就是中間了。不過該題我們不能直接拿到中間，而是要拿到中間的前一個節(jié)點，這樣才能把第一個子鏈表的末尾置為空，這里的技巧就是快慢指針循環(huán)的條件是fast.next != null && fast.next.next != null。

注意

因為不能有額外空間，我們最好用迭代的方法反轉(zhuǎn)鏈表。

代碼

public class Solution {
    public void reorderList(ListNode head) {
        if(head == null) return;
        ListNode slow = head;
        ListNode fast = head;
        // 找到中點的前一個節(jié)點
        while(fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        // 反轉(zhuǎn)中點及之后的鏈表
        ListNode head2 = reverseList(slow.next);
        // 將前半部分鏈表的末尾置空
        slow.next = null;
        // 找到兩個子鏈表的頭，準(zhǔn)備開始合并
        ListNode head1 = head;
        ListNode dummyHead = new ListNode(0);
        ListNode curr = dummyHead;
        // 當(dāng)子鏈表都不為空的時候依次合并
        while(head2 != null && head1 != null){
            curr.next = head1;
            head1 = head1.next;
            curr = curr.next;
            curr.next = head2;
            head2 = head2.next;
            curr = curr.next;
        }
        // 當(dāng)其中一個子鏈表為空時，把另一個鏈表剩下的那個節(jié)點加上，因為可能一共有奇數(shù)個節(jié)點
        curr.next = head2 != null ? head2 : null;
        curr.next = head1 != null ? head1 : null;
        head = dummyHead.next;
    }
    
    // 迭代反轉(zhuǎn)鏈表
    private ListNode reverseList(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode p1 = head;
        ListNode p2 = head.next;
        while(p2 != null){
            ListNode tmp = p2.next;
            p2.next = p1;
            p1 = p2;
            p2 = tmp;
        }
        head.next = null;
        return p1;
    }
}