P143 Reorder List

2019-11-06 06:45:21

字體：大中小

來源：轉載

供稿：網友

問題描述

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}.

實現思路

具體代碼

// ListNode 的定義 class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; } } /* * Solution1：通過數組記錄原來鏈表的順序，來進行reorder */ public void reorderList(ListNode head) { // 如果head為Null，則返回 if(head == null) return; // 遍歷鏈表，將其放到數組中 ArrayList<ListNode> arr = new ArrayList<ListNode>(); ListNode newHead = new ListNode(0), curNode = head; while(curNode != null) { arr.add(curNode); curNode = curNode.next; } // 當前節點指向newHead curNode = newHead; // 同時從前向后，從后向前遍歷數組 for(int i=0, j = arr.size()-1; i<=j; i++, j--) { curNode.next = arr.get(i); curNode = curNode.next; if(i < j) { // 處理 i == j的情況，i==j的話則不插入 curNode.next = arr.get(j); curNode = curNode.next; } } // 將當前節點的next置為空 curNode.next = null; // 將head.next置為newHead.next.next head.next = newHead.next.next; } /* * Solution 2：在鏈表上分為三步，進行reorder */ public void reorderList2(ListNode head){ if(head == null) return; ListNode p1 = head, p2 = head; ListNode curNode = null; //記錄中心點后面鏈表反轉后的頭部 // Step 1: 找到中心點 1->2->3->4->5 or 1->2->3->4->5->6 while(p2.next != null && p2.next.next != null) { p1 = p1.next; p2 = p2.next.next; } // Step 2: 從中心點斷開，把中心點后面的鏈表進行反轉 1->2->3 5->4 or 1->2->3 6->5->4 p2 = p1.next; p1.next = null; while(p2 != null) { ListNode next = p2.next; p2.next = curNode; curNode = p2; p2 = next; } // Step 3: 依次插入兩個鏈表 p1 = head; while(curNode != null) { ListNode next = p1.next, next2 = curNode.next; p1.next = curNode; curNode.next = next; p1 = next; curNode = next2; } }

上一篇：選擇排序。

下一篇：Redis緩存技術在windows上的應用