leetcode/InsertionSortList.java at master · Susheng/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


/**
 * Sort a linked list using insertion sort.
 *
 */

publicclassInsertionSortList {
publicListNodeinsertionSortList(ListNodehead) {
ListNoderet = newListNode(Integer.MIN_VALUE);
ListNoderesult = ret;
ListNodecur = newListNode(0);
cur.next = head;
while (cur.next != null) {
while (result.next != null && cur.next.val > result.next.val) {
result = result.next;
 }
ListNodetmp = cur.next;
cur.next = cur.next.next;
if (result.next == null) {
result.next = tmp;
tmp.next = null;
 } else {
ListNodetmp2 = result.next;
result.next = tmp;
tmp.next = tmp2;
 }
result = ret;
 }
returnresult.next;
	}
}