資訊專欄INFORMATION COLUMN
摘要：要找到后半部分的起點(diǎn)，就是用快慢指針。不過該題我們不能直接拿到中間，而是要拿到中間的前一個(gè)節(jié)點(diǎn)，這樣才能把第一個(gè)子鏈表的末尾置為空，這里的技巧就是快慢指針循環(huán)的條件是。注意因?yàn)椴荒苡蓄~外空間，我們最好用迭代的方法反轉(zhuǎn)鏈表。
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}
.
逆序合并法 復(fù)雜度時(shí)間 O(N) 空間 O(1)
思路理想情況下，如果能一個(gè)指針從后往前走，一個(gè)指針從前往后走，然后一個(gè)一個(gè)合并就行了。但是單鏈表并沒有從后往前走的能力，難道要改造成雙鏈表嗎？其實(shí)不用，我們只要把后半部分反轉(zhuǎn)一下，變成兩個(gè)鏈表就行了。要找到后半部分的起點(diǎn)，就是用快慢指針。從頭開始，快指針走兩步，慢指針走一步，這樣快指針到頭的時(shí)候慢指針就是中間了。不過該題我們不能直接拿到中間，而是要拿到中間的前一個(gè)節(jié)點(diǎn)，這樣才能把第一個(gè)子鏈表的末尾置為空，這里的技巧就是快慢指針循環(huán)的條件是fast.next != null && fast.next.next != null。
注意因?yàn)椴荒苡蓄~外空間，我們最好用迭代的方法反轉(zhuǎn)鏈表。
代碼public class Solution {
public void reorderList(ListNode head) {
if(head == null) return;
ListNode slow = head;
ListNode fast = head;
// 找到中點(diǎn)的前一個(gè)節(jié)點(diǎn)
while(fast.next != null && fast.next.next != null){
fast = fast.next.next;
slow = slow.next;
}
// 反轉(zhuǎn)中點(diǎn)及之后的鏈表
ListNode head2 = reverseList(slow.next);
// 將前半部分鏈表的末尾置空
slow.next = null;
// 找到兩個(gè)子鏈表的頭，準(zhǔn)備開始合并
ListNode head1 = head;
ListNode dummyHead = new ListNode(0);
ListNode curr = dummyHead;
// 當(dāng)子鏈表都不為空的時(shí)候依次合并
while(head2 != null && head1 != null){
curr.next = head1;
head1 = head1.next;
curr = curr.next;
curr.next = head2;
head2 = head2.next;
curr = curr.next;
}
// 當(dāng)其中一個(gè)子鏈表為空時(shí)，把另一個(gè)鏈表剩下的那個(gè)節(jié)點(diǎn)加上，因?yàn)榭赡芤还灿衅鏀?shù)個(gè)節(jié)點(diǎn)
curr.next = head2 != null ? head2 : null;
curr.next = head1 != null ? head1 : null;
head = dummyHead.next;
}
// 迭代反轉(zhuǎn)鏈表
private ListNode reverseList(ListNode head){
if(head == null || head.next == null){
return head;
}
ListNode p1 = head;
ListNode p2 = head.next;
while(p2 != null){
ListNode tmp = p2.next;
p2.next = p1;
p1 = p2;
p2 = tmp;
}
head.next = null;
return p1;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64628.html
摘要：鏈表題目的集合雙指針法找中點(diǎn)，分割，合并，翻轉(zhuǎn)，排序。主函數(shù)對(duì)于長(zhǎng)度為或的鏈表，返回找到中點(diǎn)分割鏈表并翻轉(zhuǎn)后半段為與前半段合并。當(dāng)移動(dòng)到最后一個(gè)元素，正好移動(dòng)到整個(gè)鏈表的頭部。 Problem Given a singly linked list L: L0 → L1 → … → Ln-1 → Ln reorder it to: L0 → Ln → L1 → Ln-1 → L2 → L...
摘要：題目鏈接題目分析給定一個(gè)數(shù)組，每一個(gè)元素是一條日志。剩余部分為全為小寫字母的字符串稱為字符日志或全為數(shù)字的字符串稱為數(shù)字日志。給定的數(shù)組中確定會(huì)至少有一個(gè)字母。遍歷完成后，對(duì)字符日志進(jìn)行排序。在其后拼接數(shù)字日志數(shù)組，并返回即可。 D54 937. Reorder Log Files 題目鏈接 937. Reorder Log Files 題目分析 給定一個(gè)數(shù)組，每一個(gè)元素是一條日志。 ...
Problem Given a singly linked list L: L0→L1→…→Ln-1→Ln,reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→… You may not modify the values in the lists nodes, only nodes itself may be changed. Example 1: Given 1->2->...
摘要：有效三角形的個(gè)數(shù)雙指針最暴力的方法應(yīng)該是三重循環(huán)枚舉三個(gè)數(shù)字?？偨Y(jié)本題和三數(shù)之和很像，都是三個(gè)數(shù)加和為某一個(gè)值。所以我們可以使用歸并排序來(lái)解決這個(gè)問題。注意因?yàn)闅w并排序需要遞歸，所以空間復(fù)雜度為 ...
閱讀 2097·2021-10-08 10:21
閱讀 2491·2021-09-29 09:34
閱讀 3506·2021-09-22 15:51
閱讀 4946·2021-09-22 15:46
閱讀 2324·2021-08-09 13:42
閱讀 3447·2019-08-30 15:52
閱讀 2734·2019-08-29 17:13
閱讀 1564·2019-08-29 11:30
