Sort a linked list using insertion sort.
|
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
33
34
35
36
37
38
39
40 |
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */public
class Solution { public
ListNode insertionSortList(ListNode head) { ListNode result = null; if(head != null){ ListNode newHead = new
ListNode(0); newHead.next = head; ListNode sortedTail = head; while(sortedTail.next != null){ ListNode secondNode = sortedTail.next; ListNode searchNode = newHead; while(searchNode != secondNode){ if(searchNode.next.val > secondNode.val) break; else searchNode = searchNode.next; } if(searchNode != secondNode){ sortedTail.next = secondNode.next; secondNode.next = searchNode.next; searchNode.next = secondNode; } else sortedTail = secondNode; } result = newHead.next; } return
result; }} |
原文：http://www.cnblogs.com/averillzheng/p/3552649.html