My code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode insertionSortList(ListNode head) {
if (head == null)
return null;
else if (head.next == null)
return head;
ListNode dummy = new ListNode(Integer.MIN_VALUE);
dummy.next = head;
ListNode temp = head.next;
ListNode preTemp = head;
while (preTemp.next != null) {
ListNode fakeHead = dummy.next;
ListNode pre = dummy;
ListNode curr = temp;
while (fakeHead.val < curr.val && fakeHead != curr) {
fakeHead = fakeHead.next;
pre = pre.next;
}
if (fakeHead != curr) {
preTemp.next = temp.next;
temp.next = fakeHead;
pre.next = curr;
temp = preTemp;
}
preTemp = temp;
temp = preTemp.next;
}
return dummy.next;
}
public static void main(String[] args) {
Solution test = new Solution();
ListNode n1 = new ListNode(1);
ListNode n2 = new ListNode(2);
n2.next = n1;
System.out.println(test.insertionSortList(n2).val);
}
}
這道題目不難，但是很煩顿锰。自己也沒能做出來谨垃。
剛剛才分析過插入排序的启搂，但是一旦涉及到鏈表，就好復雜刘陶。
從第二個結(jié)點開始胳赌，遍歷之前的子鏈表，如果有值大于這個結(jié)點匙隔，就將這個結(jié)點插入到該值之前疑苫。就是 這么個思想。
這里得設置五個結(jié)點纷责。
結(jié)點1捍掺，pre 表示開始遍歷的子鏈表的頭結(jié)點的前一個結(jié)點。會不斷變化再膳，是fakeHead的上一個結(jié)點挺勿。
結(jié)點2，fakeHead 表示子鏈表的頭結(jié)點喂柒。
注意不瓶，這里fakeHead = dummy.next 而不是 head.next,因為頭結(jié)點head一直在變化，只有dummy.next 指向的才是真正的鏈表的頭結(jié)點灾杰。
結(jié)點3蚊丐，temp 子鏈表右邊一個的結(jié)點，用來被判斷插入還是不插入艳吠。
結(jié)點4麦备，preTemp temp的上一個結(jié)點
結(jié)點5，curr 用來暫存temp讲竿， 這個結(jié)點現(xiàn)在想來完全不需要泥兰，可以直接用temp，
因為在整個遍歷過程中题禀，temp, preTemp 都是不變的鞋诗，
遍歷的是之前的子鏈表，變化的是 fakeHead迈嘹， pre
然后還要注意的是削彬，當遍歷完了可能會有兩種情況出現(xiàn)。
找到比他小的秀仲， 那么融痛，插入進去。此時preTemp是不需要再往后移動一位的神僵。
沒找到雁刷，那么，preTemp是需要往后移動一位的保礼。然后會出現(xiàn)一些細節(jié)問題沛励。
所以做了處理责语。
如果插入進去了，就讓temp = preTemp.
然后之后統(tǒng)一執(zhí)行目派， preTemp = temp;
如果插入過了坤候，preTemp相當于沒移動。
如果沒插入企蹭，那么上面的那個if語句就進不去白筹，那么相當于向右移動了一格。
**
總結(jié)： sort list using insertion sort
**
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 insertionSortList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = head;
ListNode curr = head.next;
while (curr != null) {
if (curr.val >= pre.val) {
pre = pre.next;
curr = curr.next;
}
else {
pre.next = curr.next;
/** find one place from head to pre to insert current node */
ListNode tPre = dummy;
ListNode tCurr = dummy.next;
while (tCurr != pre.next) {
if (tCurr.val < curr.val) {
tPre = tPre.next;
tCurr = tCurr.next;
}
else {
tPre.next = curr;
curr.next = tCurr;
break;
}
}
curr = pre.next;
}
}
return dummy.next;
}
}
感覺我這次的做法谅摄，思路很清晰啊徒河。也基本是一遍過得。
如果發(fā)現(xiàn)curr < pre, 那就從鏈表頭結(jié)點 [head, pre] 遍歷送漠，找到合適的位置插入進去即可虚青。
沒什么難的。
還是之前的結(jié)論螺男。鏈表題目不難。就是煩纵穿。Array題目是考智商的下隧，不會就是想不出來。
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 insertionSortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode p = head;
ListNode p_pre = dummy;
while (p != null) {
ListNode pre = dummy;
ListNode curr = pre.next;
while (curr != p) {
if (curr.val < p.val) {
pre = pre.next;
curr = curr.next;
}
else {
p_pre.next = p.next;
pre.next = p;
p.next = curr;
p = p_pre.next;
break;
}
}
if (curr == p) {
p_pre = p_pre.next;
p = p.next;
}
}
return dummy.next;
}
}
差不多那樣吧谓媒。沒什么難的淆院，就是有點煩。
明天開始做DP了句惯。
Anyway, Good luck, Richardo! -- 08/17/2016
