143. 重排連結清單
難度中等459收藏分享切換為英文接收動态回報
給定一個單連結清單 L：L0→L1→…→L**n-1→Ln ，
将其重新排列後變為： L0→L**n→L1→L**n-1→L2→L**n-2→…
你不能隻是單純的改變節點内部的值，而是需要實際的進行節點交換。
示例 1:
給定連結清單 1->2->3->4, 重新排列為 1->4->2->3. 示例 2:
給定連結清單 1->2->3->4->5, 重新排列為 1->5->2->4->3. 方法一:儲存到線性表.
單連結清單不能由尾部開始周遊取數,隻能有頭開始周遊,
是以将所有周遊出來,儲存到線性表中,
通過前後雙指針進行連接配接,得到結果
public void reorderList(ListNode head) {
if (head == null) {
return;
}
//存到 list 中去
List<ListNode> list = new ArrayList<>();
while (head != null) {
list.add(head);
head = head.next;
}
//頭尾指針依次取元素
int i = 0, j = list.size() - 1;
while (i < j) {
list.get(i).next = list.get(j);
i++;
//偶數個節點的情況，會提前相遇
if (i == j) {
break;
}
list.get(j).next = list.get(i);
j--;
}
list.get(i).next = null;
} 方法二,(低效)整體進行遞歸
具體思路如圖所示
public void reorderList(ListNode head) {
if(head==null||head.next==null||head.next.next==null)
//當節點為空/節點是連結清單中的最後一個節點/倒數第二個節點時----說明不用再周遊下去了，直接傳回
return;
ListNode temp=head;
while(temp.next.next!=null)//找到倒數第二個節點
temp=temp.next;
temp.next.next=head.next;//将最後一個節點指向temp的後一個節點
head.next=temp.next;//将head指向最後一個節點
temp.next=null;//将倒數第二個節點的next指針域置空
reorderList(head.next.next);//遞歸調用函數完成對後續節點的處理
} 方法三:(高效)利用反轉法,中間值.進行插入
思路
- 利用快慢指針法,求對外連結表的中間節點
- 得到兩個子鍊标後,将最後一個反轉
- 然後将子連結清單中的節點依次進行連接配接,得出的結果
有關合并的解圖
public void reorderList1(ListNode head) {
if (head == null || head.next == null || head.next.next == null) {
return;
}
// 1. 找中點，讓slow指向中點，或左中點位置
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 2. 斷開中點，反轉後半部分
ListNode head2 = null, next = slow.next;
slow.next = null;
slow = next;
while (slow != null) {
next = slow.next;
slow.next = head2;
head2 = slow;
slow = next;
}
// 3. 合并連結清單head和head2
ListNode curr = head;
ListNode curr2 = head2;
while (curr != null && curr2 != null) {
next = curr.next;
curr.next = curr2;
curr2 = curr2.next;
curr.next.next = next;
curr = next;
}
} class Solution {
public void reorderList(ListNode head) {
if(head == null){
return ;
}
//1. 使用快慢指針,找對外連結表的中心節點。
// 1->2->3->4->5,中心節點為3
ListNode middle = middleNode(head);
//2. 将原始連結清單按照中心連結清單分割為兩個連結清單，并将右連結清單反轉
//2.1 原始連結清單：1->2->3->4->5 左連結清單：1->2->3 右連結清單：4->5
ListNode left = head;
ListNode right = middle.next;
middle.next = null;
//2.2 反轉右連結清單
//原始右連結清單：4->5 反轉後：5->4
right = reverse(right);
//3. 合并兩個連結清單，将右連結清單插入到左連結清單
//左連結清單：1->2->3 右連結清單：4->5 合并後：1->5->2->4->3
merge(left,right);
}
//1. 使用快慢指針,找對外連結表的中心節點
public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
//2. 通過遞歸反轉連結清單
public ListNode reverse(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode last = reverse(head.next);
head.next.next = head;
head.next = null;
return last;
}
//3. 合并兩個連結清單，将右連結清單插入到左連結清單
public void merge(ListNode left, ListNode right){
ListNode leftTemp;
ListNode rightTemp;
while (left.next != null && right!= null) {
//1. 儲存next節點
leftTemp = left.next;
rightTemp = right.next;
//2. 将右連結清單的第一個節點插入到左連結清單中
// 左連結清單：1->2->3 右連結清單：5->4
// 合并後的左連結清單：1->5->2->3
left.next = right;
right.next = leftTemp;
//3. 移動left和right指針
//左連結清單變為：2->3 右連結清單變為：4
left = leftTemp;
right = rightTemp;
}
}
}