leetCode No.143 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} .
問題を解く構想.
頭ポインタを定義し、頭ポインタが2つのノードを後ろにジャンプするたびに、ジャンプする前にチェーンテーブルの現在の最後のノードを頭ポインタの後ろに置きます.しかし一方向チェーンテーブルであるため,テールノードを探すたびに先頭からテールまで遍歴する.さらに最適化することは,エンドノードを探すときに現在の点から後ろに探すことであり,チェーンテーブルを毎回巡回する必要はないが,このような方法は依然として遅く,最終的にはTLEであることが明らかである.正しい方法は,まず速遅指針法でチェーンテーブルの中点を見つけ,中点の後のノードを遍歴しながらその場で逆順にすることである.最後に、後半のノードを前のノードに挿入します.時間複雑度はO(n)
コード#コード#

public class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null ) {
            return;
        }
        ListNode fast = head;
        ListNode slow = head;
        ListNode p = head;
        ListNode q = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        fast = slow.next;
        slow.next = null;
        p = fast;
        q = fast.next;
        fast.next = null;
        while (q != null) {
            ListNode temp = q.next;
            q.next = p;
            p = q;
            q = temp;
        }
        q = head;
        while (q != null && p != null) {
            ListNode temp1 = q.next;
            ListNode temp2 = p.next;
            p.next = q.next;
            q.next = p;
            q = temp1;
            p = temp2;
        }
    }
}

関連リンク
原題のすべての問題解コード(github)