【LeetCode】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}

.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
           

【題意】

給定一個連結清單，把最後一個結點插入到第1個結點後，倒數第二個結點插入到第2個結點後，倒數第三個結點插入到第3個結點後，以此類推……

【思路】

由題意知，後面 (n-1)/2 個結點需要分别插入到前面 (n-1)/2 個結點後。

那麼先把連結清單分為兩段，前面 n-(n-1)/2 個結點為被插傳入連結表，和後面 (n-1)/2 個結點為插傳入連結表。

在插入之前，需先把插傳入連結表逆序，即第n個結點->第n-1個結點->...

【Java代碼】

public class Solution {
    public void reorderList(ListNode head) {
        ListNode node = head;
        int cnt = 0;
        while (node != null) {
            cnt++;
            node = node.next;
        }
        
        if (cnt < 3) return;//3個以下的結點不需要移動
        
        int k = (cnt - 1) / 2;//需要移動的後k個結點
        int i = 1;
        node = head;
        while (i++ < cnt - k) {
            node = node.next;
        }
        ListNode begin = node.next;//用begin表示需要移動的後k個結點的開始
        node.next = null;//把不需要移動的部分結尾設為null
        
        //把需要移動的k個結點逆序
        ListNode pre = begin;
        ListNode cur = begin.next;
        begin.next = null;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            
            begin = cur;
            pre = cur;
            cur = next;
        }
        
        ListNode node1 = head;
        ListNode node2 = begin;
        while (node1 != null && node2 != null) {
            pre = node1;
            cur = node2;
            
            node1 = node1.next;//這兩行一定要放在下面兩行之前，因為pre和node1指向同一個結點，下面操作會改變node1的next；cur和node2同理
            node2 = node2.next;
            
            cur.next = pre.next;//這兩行代碼是把cur插入到pre後
            pre.next = cur;
        }
    }
}
           

【感受】

代碼寫起來超惡心，寫着寫着就混亂了，一會兒就不知道next指的是哪個結點了。

【更新版】

先用快慢指針找到連結清單的中點，然後翻轉連結清單後半部分，再和前半部分組合。

需要注意的是把連結清單分成兩半時，前半段的尾節點要置為NULL，翻轉連結清單時也要把尾節點置為NULL。

public class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        
        //把整個連結清單劃分成2個等長的子連結清單，如果原連結清單長度為奇數，那麼第一個子連結清單的長度多1
        ListNode slow = head, fast = head;
        while (fast.next != null) {
            fast = fast.next;
            if (fast.next != null) fast = fast.next;
            else break;
            slow = slow.next;
        }
        
        ListNode head1 = head, head2 = slow.next;
        slow.next = null;
        
        //翻轉第二個子連結清單
        ListNode cur = head2, post = cur.next;
        cur.next = null;
        while (post != null) {
            ListNode tmp = post.next;
            post.next = cur;
            cur = post;
            post = tmp;
        }
        head2 = cur;
        
        //将兩個子連結清單合并
        ListNode node1 = head1, node2 = head2;
        while (node2 != null) {
            ListNode tmp1 = node1.next;
            ListNode tmp2 = node2.next;
            node1.next = node2;
            node2.next = tmp1;
            node1 = tmp1;
            node2 = tmp2;
        }
    }
}