1.想法
1.從題目的題意可知,我們需要三步,
step 1:將現(xiàn)有的鏈表分成兩個部分1.L0→L中 2.L中+1→Ln(尋找鏈表的中間節(jié)點) 快慢指針
step 2:翻轉(zhuǎn)后一部分的鏈表(翻轉(zhuǎn)鏈表) 翻轉(zhuǎn)鏈表
step 3:合并這兩部分鏈表(鏈表合并)
2.代碼
class Solution {
public void reorderList(ListNode head) {
//極端情況
if(head == null||head.next == null)return;
//1.找到中間節(jié)點
ListNode midHead = getMidNode(head);
ListNode midNext = midHead.next;
midHead.next = null;
//2.翻轉(zhuǎn)后面的列表
ListNode midNextHead = reverseNode(midNext);
//3.結(jié)合兩個鏈表
ListNode temp = head,l0 = head.next,l1 = midNextHead;
temp.next = l1;
l1= l1.next;
temp = temp.next;
while(l1!=null){
temp.next = l0;
l0 = l0.next;
temp = temp.next;
temp.next =l1;
l1 = l1.next;
temp = temp.next;
}
if(l0!=null){
temp.next = l0;
}
}
private ListNode reverseNode(ListNode midNext) {
ListNode pre = null,now = midNext,next = now.next;
while(next!=null){
now.next = pre;
pre = now;
now = next;
next = now.next;
}
now.next = pre;
return now;
}
private ListNode getMidNode(ListNode head) {
ListNode mid = head;
int count = 1;
while(head.next!=null){
head = head.next;
count++;
if(count%2!=0){
mid = mid.next;
}
}
return mid;
}
}
