NC2 重排連結清單

描述

将給定的單連結清單\ L L： L_0→L_1→…→L_{n-1}→L_ nL0​→L1​→…→Ln−1​→Ln​

重新排序為：L_0→L_n →L_1→L_{n-1}→L_2→L_{n-2}→…L0​→Ln​→L1​→Ln−1​→L2​→Ln−2​→…

要求使用原地算法，不能隻改變節點内部的值，需要對實際的節點進行交換。

示例1

輸入：

{1,2,3,4}      

複制傳回值：

{1,4,2,3}      

複制說明：

給定head連結清單1->2->3->4, 重新排列為 1->4->2->3,會取head連結清單裡面的值列印輸出         

示例2

輸入：

{1,2,3,4,5}      

複制傳回值：

{1,5,2,4,3}      

複制說明：

給定head連結清單1->2->3->4->5, 重新排列為 1->5>2->4->3,會取head連結清單裡面的值列印輸出       

線性表

我們都知道連結清單的缺點是查詢效率低，每一次都需要從頭開始周遊。是以如果按照題目的要求組成新連結清單，要去得到最後一個節點，就得從頭将連結清單周遊一次，這樣反複操作，直到将原來的連結清單改變到題目要求的連結清單。這樣很明顯是非常耗時間的。、

由于有了上面的分析，直到了這一缺點，我們就可以想到與連結清單齊名的

數組

了。

我們知道

數組

想通路某一個元素的時候，可以通過下标直接去通路它，這不就是我們想要的嗎？

是以下面我們先來一個簡單粗暴的方法，因為我們知道

ArrayList

的底層就是用數組實作的，是以我們将連結清單儲存在一個

ArrayList

中，然後利用雙指針，一個指向最前面，一個指向最後面，依次通路并向題目要求的連結清單形式進行轉換！

class Solution {
    public void reorderList(ListNode head) {
        if(head == null)
            return;
        List<ListNode> list = new ArrayList<>();   //  ArrayList為線性表
        // 将 連結清單的每一個節點依次 存進ArrayList中
        while(head != null){
            list.add(head);
            head = head.next;
        }
        // 兩個指正依次從前 後進行周遊取元素
        int i = 0, j = list.size()-1;
        while(i < j){
            //  eg:  1->2->3->4
            // 前面的節點的下一個節點指向最後的節點
            list.get(i).next = list.get(j);  //  即 1->4
            i++;  // 此時 i++ 則此時 list.get(i) 為原來前面節點的下一個節點   即節點2
            if(i == j) // 若 連結清單長度為偶數的情況下 則會提前相遇，此時已達到題目要求，直接終止循環
                break;
            list.get(j).next = list.get(i);   // 4->2
            // 此時剛剛的例子則變為  1->4->2->3
            j--;
        }
        list.get(i).next = null;  // 最後一個節點的下一個節點為null
    }
}
           

方法2使用反轉連結清單

三步走

eg： 1->2->3->4->5->6

第一步：将連結清單分為兩個連結清單

​ 1->2->3 4->5->6

第二步：将第二個連結清單逆序

​ 1->2->3 6->5->4

第三步：依次連接配接兩個連結清單 連接配接形式如下

​ 1->6->2->5->3->4

public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        ListNode mid = middleNode(head);
        ListNode l1 = head;
        ListNode l2 = mid.next;
        mid.next = null;
        l2 = reverseList(l2);
        mergeList(l1, l2);
    }

    public ListNode middleNode(ListNode head) {//找中間節點
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public ListNode reverseList(ListNode head) {//反轉第二個連結清單
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    public void mergeList(ListNode l1, ListNode l2) {//合并兩個連結清單
        ListNode l1_tmp;
        ListNode l2_tmp;
        while (l1 != null && l2 != null) {
            l1_tmp = l1.next;
            l2_tmp = l2.next;

            l1.next = l2;
            l1 = l1_tmp;

            l2.next = l1;
            l2 = l2_tmp;
        }
    }