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);
}
}
这道题目不难，但是很烦。自己也没能做出来。
刚刚才分析过插入排序的，但是一旦涉及到链表，就好复杂。
从第二个结点开始，遍历之前的子链表，如果有值大于这个结点，就将这个结点插入到该值之前。就是 这么个思想。
这里得设置五个结点。
结点1，pre 表示开始遍历的子链表的头结点的前一个结点。会不断变化，是fakeHead的上一个结点。
结点2，fakeHead 表示子链表的头结点。
注意，这里fakeHead = dummy.next 而不是 head.next,因为头结点head一直在变化，只有dummy.next 指向的才是真正的链表的头结点。
结点3，temp 子链表右边一个的结点，用来被判断插入还是不插入。
结点4，preTemp temp的上一个结点
结点5，curr 用来暂存temp， 这个结点现在想来完全不需要，可以直接用temp，
因为在整个遍历过程中，temp, preTemp 都是不变的，
遍历的是之前的子链表，变化的是 fakeHead， pre
然后还要注意的是，当遍历完了可能会有两种情况出现。
找到比他小的， 那么，插入进去。此时preTemp是不需要再往后移动一位的。
没找到，那么，preTemp是需要往后移动一位的。然后会出现一些细节问题。
所以做了处理。
如果插入进去了，就让temp = preTemp.
然后之后统一执行， preTemp = temp;
如果插入过了，preTemp相当于没移动。
如果没插入，那么上面的那个if语句就进不去，那么相当于向右移动了一格。
**
总结： 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;
}
}
感觉我这次的做法，思路很清晰啊。也基本是一遍过得。
如果发现curr < pre, 那就从链表头结点 [head, pre] 遍历，找到合适的位置插入进去即可。
没什么难的。
还是之前的结论。链表题目不难。就是烦。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
