143. 重排鏈表

給定一個(gè)單鏈表 L：L0→L1→…→Ln-1→Ln ，
將其重新排列后變?yōu)椋?L0→Ln→L1→Ln-1→L2→Ln-2→…

• 你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換。

示例1:

給定鏈表 1->2->3->4, 重新排列為 1->4->2->3.

示例2:

給定鏈表 1->2->3->4->5, 重新排列為 1->5->2->4->3.

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/reorder-list/
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

• 1.入棧法

思路：(使用棧進(jìn)行反轉(zhuǎn))

1. 使用快慢指針找到鏈表中點(diǎn)
2. 將鏈表中點(diǎn)之后的元素壓入棧
3. 依次將元素出棧（目的是反轉(zhuǎn)）然后進(jìn)行拼接即可

• 注意：找到鏈表中點(diǎn)之后，一定要將后面置空

public static class ListNode {

        private int val;
        private ListNode next;

        public ListNode(int val) {
            this.val = val;
        }

        //用于測試用例
        public ListNode(int[] arr) {
            if (arr == null || arr.length == 0) throw new NullPointerException("array is Empty");
            this.val = arr[0];
            ListNode cur = this;
            for (int i = 1; i < arr.length; i++) {
                cur.next = new ListNode(arr[i]);
                cur = cur.next;
            }
        }

        @Override
        public String toString() {
            StringBuilder res = new StringBuilder();
            ListNode cur = this;
            while (cur != null) {
                res.append(cur.val + "->");
                cur = cur.next;
            }
            res.append("NULL");
            return res.toString();
        }

    }

   private static void reordList2(ListNode head) {
        if (head == null) return;
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        Stack<ListNode> stack = new Stack<>();
        ListNode next = slow.next;
        while (next != null) {
            stack.push(next);
            next = next.next;
        }
        slow.next = null;
        ListNode cur = head;
        while (!stack.isEmpty()) {
            ListNode node = new ListNode(stack.pop().val);
            node.next = cur.next;
            cur.next = node;
            cur = cur.next.next;
        }
    }

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(n + n / 2 + n / 2), 時(shí)間復(fù)雜度是遍歷鏈表 + 遍歷右半部分鏈表 + 遍歷棧

• 空間復(fù)雜度：O(n / 2 + n / 2), 空間復(fù)雜度為 棧所占用的空間 + 新建的鏈表所占用的空間

• 2. 反轉(zhuǎn)+指針

思路：優(yōu)化方法1

1. 先使用快慢指針找到整個(gè)鏈表的中點(diǎn)
2. 將中點(diǎn)后面的后半部分鏈表進(jìn)行反轉(zhuǎn)

3. 將反轉(zhuǎn)后的鏈表拼接到原鏈表即可

   
   
   image.png

  private static void reordList(ListNode head) {
        if (head == null) return;
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //將后半部分鏈表反轉(zhuǎn)
        ListNode rev = reverse2(slow.next);
        //將鏈表斷開
        slow.next = null;
        ListNode cur = head;
        while (rev != null) {
            ListNode p = rev.next;
            rev.next = cur.next;
            cur.next = rev;
            rev = p;
            cur = cur.next.next;
        }
    }
    
     /**
     * 反轉(zhuǎn)鏈表
     * @param head
     * @return
     */
    private static ListNode reverse(ListNode head) {
        ListNode prev  = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

    /**
     * 遞歸反轉(zhuǎn)
     * @param head
     * @return
     */
    private static ListNode reverse2(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode cur = reverse2(head.next);
        head.next.next = head;
        head.next = null;
        return cur;
    }
    

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(n + n/2): n為鏈表長度, 復(fù)雜度為兩次遍歷的時(shí)間

• 空間復(fù)雜度：O(1)

• 測試用例

public static void main(String[] args) {
        int[] arr = new int[] {1, 2, 3, 4, 5};
        ListNode listNode = new ListNode(arr);
        System.out.println(listNode);
        System.out.println("重排鏈表" + reordList(listNode));
    } 

• 結(jié)果

1->2->3->4->5->NULL
重排鏈表1->5->2->4->3->NULL

• 源碼

• 我會(huì)每天更新新的算法，并盡可能嘗試不同解法，如果發(fā)現(xiàn)問題請指正

• Github