Question:
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}.
My code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null || head.next.next == null)
return;
ListNode temp = head;
int count = 1; //record the amount of the total nodes
while (temp.next != null) {
temp = temp.next;
count++;
}
// get the middle node of this linked list
int middle = count / 2;
ListNode middleNode = head;
for (int i = 1; i < middle; i++)
middleNode = middleNode.next;
// reverse the right half linked list
ListNode tail = middleNode;
for (int i = middle; i < count; i++)
tail = tail.next;
reverseLinkedList(middleNode.next);
middleNode.next = tail;
// insert nodes
temp = head;
ListNode rightHead = middleNode.next;
ListNode temp2 = null;
int i = 1;
while (i < middle) {
temp2 = rightHead.next;
rightHead.next = temp.next;
temp.next = rightHead;
temp = rightHead.next;
rightHead = temp2;
middleNode.next = rightHead;
i++;
}
}
private ListNode reverseLinkedList(ListNode head) {
if (head == null)
return null;
ListNode temp = reverseLinkedList(head.next);
if (temp == null)
return head;
temp.next = head;
head.next = null;
return head;
}
}
My test result:
這次作業(yè)一開始我是用另外一種方法寫的眠副，遞歸画切。但是我自己也知道，復(fù)雜度太大了囱怕。提交代碼后發(fā)現(xiàn)霍弹，果然超出限定時間了。于是只能去看網(wǎng)友的提示光涂。然后寫出了現(xiàn)在的代碼庞萍。
他把這個reorder分為了三個步驟。
第一個步驟忘闻，找到 middle node.
第二個步驟钝计，reverse 后半段 鏈表。
第三個步驟齐佳，一個個插入進(jìn)去私恬。
為什么我沒能想到呢？我喜歡思考這個問題炼吴。
還是那個原因本鸣，同樣的問題，我們的出發(fā)點不同硅蹦，導(dǎo)致最后寫出來的復(fù)雜度就完全不同了荣德。
不過，趁這個機會童芹，復(fù)習(xí)了下reverse the linked list涮瞻，同時，第三個步驟插入假褪，需要有個將后半段與前半段鏈表連接起來的小操作署咽。
貼一下我自己寫的代碼：
public class Solution {
public void reorderList(ListNode head) {
if (head == null)
return;
reorder(head);
}
private void reorder(ListNode head) {
if (head.next == null)
return;
ListNode subListHead = head.next;
ListNode temp = subListHead;
if (temp.next == null)
return;
while (temp.next.next != null)
temp = temp.next;
ListNode subListTail = temp.next;
if (subListTail == subListHead.next) {
head.next = subListTail;
subListTail.next = subListHead;
subListHead.next = null;
return;
}
else {
temp.next = null;
head.next = subListTail;
subListTail.next = subListHead;
reorder(subListHead);
}
}
}
**
總結(jié)：當(dāng)復(fù)雜度過高的時候，就不是寫代碼的問題了生音，是你思考問題的角度不對宁否。這個時候就像換種想法去解決這個問題了，而不要固守在這個問題上缀遍。
反轉(zhuǎn)鏈表： 遞歸的話慕匠，就是。域醇。台谊。冤寿。好，我腦子里想了一遍青伤，就不打出來了，不知道怎么表達(dá)殴瘦。
**
本來想專心學(xué)習(xí)CS一段時間的狠角，但發(fā)現(xiàn)還是有好多事情等著自己去做。
機票還沒買蚪腋。
日本行丰歌。
家里那么多親戚，爸媽的朋友都等著請我吃飯屉凯。
高中同學(xué)立帖。
哎，好多事悠砚。
我現(xiàn)在最想的晓勇，就是給我一年的時間，讓我安靜學(xué)習(xí)下計算機灌旧，我真的感興趣绑咱。
昨天出去散步，路上回家枢泰，碰到了小學(xué)的班主任描融。她還記得我。哈哈衡蚂，我這么優(yōu)秀她怎么會忘了我窿克。我覺得我應(yīng)該是我小學(xué)班上的異類吧。我的小學(xué)算是鄉(xiāng)下毛甲，班里的大多數(shù)現(xiàn)在都工作了年叮，有些已經(jīng)結(jié)婚了，甚至有小孩了丽啡。
而我谋右，還在作死。
把自己這幾年念的大學(xué)和老師講了补箍。改执。。結(jié)果她一所都沒聽過坑雅。
我本來想衣錦還鄉(xiāng)的辈挂，現(xiàn)在。裹粤。终蒂。怎么還鄉(xiāng)。。拇泣。
Anyway, Good luck, Richardo!
My code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null) {
return;
}
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode head2 = slow.next;
slow.next = null;
fast = reverse(head2);
slow = head;
ListNode dummy = new ListNode(-1);
ListNode curr = dummy;
while (slow != null && fast != null) {
curr.next = slow;
slow = slow.next;
curr = curr.next;
curr.next = fast;
fast = fast.next;
curr = curr.next;
}
if (slow != null) {
curr.next = slow;
}
}
private ListNode reverse(ListNode head) {
ListNode pre = head;
ListNode curr = head.next;
while (curr != null) {
ListNode next = curr.next;
curr.next = pre;
pre = curr;
curr = next;
}
head.next = null;
return pre;
}
}
這道題目沒什么難點噪叙。就是找到中點，然后斷開其與下一個節(jié)點的聯(lián)系霉翔。然后reverse右半部分的鏈表睁蕾，然后merge
Anyway, Good luck, Richardo! -- 08/16/2016
