My code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode sortList(ListNode head) {
if (head == null)
return null;
int count = 0;
ListNode temp = head;
while (temp != null) {
count++;
temp = temp.next;
}
return sortList(head, count);
}
private ListNode sortList(ListNode head, int count) {
if (count <= 1)
return head;
int left = 0;
int right = 0;
if (count % 2 == 0)
left = count / 2;
else
left = count / 2 + 1;
right = count - left;
ListNode leftHead = head;
ListNode rightHead = null;
int countNode = 0;
ListNode temp = head;
while (temp != null) {
countNode++;
if (countNode == left) {
rightHead = temp.next;
temp.next = null;
break;
}
else
temp = temp.next;
}
ListNode subLeftHead = sortList(leftHead, left);
ListNode subRightHead = sortList(rightHead, right);
ListNode dummyNode = new ListNode(-1);
ListNode tempDummy = dummyNode;
int countLeft = 0;
int countRight = 0;
while (countLeft < left && countRight < right) {
if (subLeftHead.val <= subRightHead.val) {
tempDummy.next = subLeftHead;
subLeftHead = subLeftHead.next;
tempDummy = tempDummy.next;
countLeft++;
}
else {
tempDummy.next = subRightHead;
subRightHead = subRightHead.next;
tempDummy = tempDummy.next;
countRight++;
}
}
if (countLeft == left)
tempDummy.next = subRightHead;
else
tempDummy.next = subLeftHead;
return dummyNode.next;
}
public static void main(String[] args) {
ListNode n1 = new ListNode(8);
ListNode n2 = new ListNode(7);
ListNode n3 = new ListNode(6);
ListNode n4 = new ListNode(5);
ListNode n5 = new ListNode(4);
ListNode n6 = new ListNode(3);
ListNode n7 = new ListNode(2);
ListNode n8 = new ListNode(1);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n6;
n6.next = n7;
n7.next = n8;
Solution test = new Solution();
ListNode head = test.sortList(n1);
while (head != null) {
System.out.println(head.val);
head = head.next;
}
}
}
My test result:
這次作業(yè)說實話不難凿渊，但是要完全寫出來還是有點細(xì)節(jié)的梁只。
首先，一開始我很難理解埃脏，鏈表麻痹怎么排序啊搪锣，還是歸并排序。
后來發(fā)現(xiàn)必須得統(tǒng)計結(jié)點個數(shù)彩掐，接下來就好做點了构舟。
用遞歸么，一層層遞歸下去堵幽，用普林斯頓算法課的說法叫做狗超， bottom -up.
分成一塊一塊，然后再一塊塊拼裝起來朴下。
思想還是歸并排序的思想努咐，在這里我想說一個小技巧，那就是殴胧， dummy node.
真的很好用渗稍，尤其對于鏈表佩迟，很多復(fù)雜情況不需要在考慮了。
還有這里有個細(xì)節(jié)竿屹，
因為我們要把一個鏈表切成兩段报强，然后分別遞歸，事實上這兩個子鏈表還是連接在一起的拱燃，所以我們需要人為得把他們切斷秉溉，
即 temp.next = null;
然后再遞歸。這是一個注意點扼雏。
同時坚嗜，鏈表操作我還是有些地方?jīng)]注意到，像這道題目诗充，通過dummy node來將兩個子鏈表合二為一，并且排序诱建，沒有用到額外的空間蝴蜓，dummy node 就像是細(xì)線一樣，將這些結(jié)點重新串在了一塊兒俺猿。
**
總結(jié)： Merge Sort, LinkedList, Recursion
剛寫代碼茎匠，一個很久以前的朋友突然找我，上來第一句話就是押袍，
以后去哪里發(fā)展诵冒？
很有社會上的口氣。我就和他聊了開來谊惭，一開始是有提防心的汽馋，比如他問我在不在家，之類的圈盔，我都回避豹芯，但聊著聊著就聊開了。某人估計又要罵我傻逼了吧驱敲。
他要結(jié)婚了铁蹈，然后一直說我了不起，本科众眨，研究生的大學(xué)都很強(qiáng)握牧，學(xué)歷高。
說真的娩梨，我從來沒覺得我的學(xué)校很強(qiáng)沿腰，覺得可以拿這個去比，從來沒覺得姚建。
但是矫俺，從他嘴中，我了解到了社會，尤其中國社會厘托，原來這么看重學(xué)歷友雳。甚至高中是哪里的都很看重。那我應(yīng)該更加自信點了铅匹，雖然以前我一直覺得一個人該有相當(dāng)?shù)谋臼略儆邢喈?dāng)?shù)淖孕叛荷蓿F(xiàn)在看來，學(xué)歷也是那么重要包斑，即使你什么都不會流礁。
但是，我現(xiàn)在很努力罗丰，為什么神帅？就像我之前努力出國，為什么萌抵，真的不是為了學(xué)歷找御。。當(dāng)然學(xué)校是否有名也是有考慮的绍填，但更多的霎桅，是想有一個好的環(huán)境讓我去學(xué)習(xí)技術(shù)。所以其實我的出發(fā)點還是比較純潔的讨永，這也可能是我為什么能持續(xù)走下去的原因之一吧滔驶，因為我真的有這個需求，我很想學(xué)習(xí)這方面的知識卿闹。
女朋友的事揭糕，我這幾天是有點操之過急了，畢竟她才培訓(xùn)一個禮拜啊比原，那么忙插佛，身體也那么累，不像我回家還休息了一兩天量窘，然后之后也是懶散的學(xué)習(xí)雇寇。我真的把她當(dāng)成了機(jī)器，雖然我的本心是好的蚌铜，但我就是把她當(dāng)成了機(jī)器锨侯，按照我的設(shè)計而去學(xué)習(xí)。這是不對的冬殃。
但同樣囚痴，她也還是不夠拼命，也許還沒開始吧审葬。希望下周可以真正開始了深滚。
Because TOEFL is on the way.
**
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 ListNode sortList(ListNode head) {
if (head == null)
return null;
return sort(head);
}
/** sort this list */
private ListNode sort(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode slow = head;
ListNode fast = head;
/** find the middle node in the linkedlist using slow and fast pointers */
while (fast.next != null && fast.next.next != null) {
slow = slow.next; // jump 1 node for slow pointer
fast = fast.next; // jump 2 nodes for fast pointer
fast = fast.next;
}
ListNode leftHead = head;
ListNode rightHead = slow.next;
slow.next = null; // cut the connection between left and right sub linked list
/** sort these two sub linked lists separately */
leftHead = sort(leftHead); // make sure this sub lis is sorted
rightHead = sort(rightHead);
/** merge them into one sorted linked list */
return merge(leftHead, rightHead);
}
/** merge these two sub sorted lists */
private ListNode merge(ListNode leftHead, ListNode rightHead) {
if (leftHead == rightHead)
return leftHead;
ListNode leftScanner = leftHead;
ListNode rightScanner = rightHead;
ListNode head;
/** ensure the head node */
if (leftHead.val < rightHead.val) {
head = leftHead;
leftScanner = leftScanner.next;
}
else {
head = rightHead;
rightScanner = rightScanner.next;
}
ListNode scanner = head;
/** merge two linked lists until one of them is finished */
while (leftScanner != null && rightScanner != null) {
if (leftScanner.val < rightScanner.val) {
scanner.next = leftScanner;
leftScanner = leftScanner.next;
}
else {
scanner.next = rightScanner;
rightScanner = rightScanner.next;
}
scanner = scanner.next;
}
/** connect the rest of the other list to this new sorted list */
if (leftScanner == null)
scanner.next = rightScanner;
else
scanner.next = leftScanner;
return head;
}
public static void main(String[] args) {
Solution test = new Solution();
ListNode a0 = new ListNode(3);
ListNode a1 = new ListNode(2);
ListNode a2 = new ListNode(4);
a0.next = a1;
a1.next = a2;
ListNode head = test.sortList(a0);
while (head != null) {
System.out.println(head.val);
head = head.next;
}
}
}
這道題目寫了一會兒奕谭。以前的寫法是不對的。因為我聲明了一個dummy node需要內(nèi)存痴荐，然后一層層下來就是血柳， log(n) 的復(fù)雜度，就不再是常數(shù)級別了生兆。
然后其他就差不多了难捌，就是 merge sort the linked list
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 ListNode sortList(ListNode head) {
return helper(head);
}
private ListNode helper(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode right = slow.next;
ListNode left = head;
slow.next = null;
left = helper(left);
right = helper(right);
return merge(left, right);
}
private ListNode merge(ListNode leftHead, ListNode rightHead) {
if (leftHead == null) {
return rightHead;
}
else if (rightHead == null) {
return leftHead;
}
ListNode left = leftHead;
ListNode right = rightHead;
ListNode dummy = new ListNode(-1);
ListNode curr = dummy;
while (left != null || right != null) {
if (left == null) {
curr.next = right;
curr = curr.next;
right = right.next;
}
else if (right == null) {
curr.next = left;
curr = curr.next;
left = left.next;
}
else if (left.val < right.val) {
curr.next = left;
curr = curr.next;
left = left.next;
}
else {
curr.next = right;
curr = curr.next;
right = right.next;
}
}
return dummy.next;
}
}
這道題目本身沒有什么難度⊙荒眩空間復(fù)雜度是O(1),雖然用了dummy node,但是是在merge中使用的根吁，使用完了后立刻釋放。
Anyway, Good luck, Richardo! -- 08/17/2016
