|
5 | 5 | importjava.util.ArrayList; |
6 | 6 | importjava.util.List; |
7 | 7 |
|
8 | | -/** |
9 | | - * 147. Insertion Sort List |
10 | | - * |
11 | | - * Sort a linked list using insertion sort. |
12 | | - * |
13 | | - * Algorithm of Insertion Sort: |
14 | | - * |
15 | | - * Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. |
16 | | - * At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. |
17 | | - * It repeats until no input elements remain. |
18 | | - * |
19 | | - * |
20 | | - * Example 1: |
21 | | - * |
22 | | - * Input: 4->2->1->3 |
23 | | - * Output: 1->2->3->4 |
24 | | - * |
25 | | - * Example 2: |
26 | | - * |
27 | | - * Input: -1->5->3->4->0 |
28 | | - * Output: -1->0->3->4->5 |
29 | | - */ |
30 | 8 | publicclass_147 { |
31 | 9 |
|
32 | | -publicstaticclassSolution1 { |
33 | | -publicListNodeinsertionSortList(ListNodehead) { |
34 | | -ListNodetemp =head; |
35 | | -List<Integer>list =newArrayList<>(); |
36 | | -while (temp !=null) { |
37 | | -list.add(temp.val); |
38 | | -temp =temp.next; |
39 | | - } |
40 | | -Integer[]nums =list.toArray(newInteger[list.size()]); |
41 | | -for (inti =1;i <list.size();i++) { |
42 | | -for (intj =i -1;j >=0;j--) { |
43 | | -if (nums[j] >nums[j +1]) { |
44 | | -inttempNum =nums[j]; |
45 | | -nums[j] =nums[j +1]; |
46 | | -nums[j +1] =tempNum; |
47 | | - } |
| 10 | +publicstaticclassSolution1 { |
| 11 | +publicListNodeinsertionSortList(ListNodehead) { |
| 12 | +ListNodetemp =head; |
| 13 | +List<Integer>list =newArrayList<>(); |
| 14 | +while (temp !=null) { |
| 15 | +list.add(temp.val); |
| 16 | +temp =temp.next; |
| 17 | + } |
| 18 | +Integer[]nums =list.toArray(newInteger[list.size()]); |
| 19 | +for (inti =1;i <list.size();i++) { |
| 20 | +for (intj =i -1;j >=0;j--) { |
| 21 | +if (nums[j] >nums[j +1]) { |
| 22 | +inttempNum =nums[j]; |
| 23 | +nums[j] =nums[j +1]; |
| 24 | +nums[j +1] =tempNum; |
| 25 | + } |
| 26 | + } |
| 27 | + } |
| 28 | +ListNodenewHead =head; |
| 29 | +for (inti =0;i <nums.length;i++) { |
| 30 | +newHead.val =nums[i]; |
| 31 | +newHead =newHead.next; |
| 32 | + } |
| 33 | +returnhead; |
48 | 34 | } |
49 | | - } |
50 | | -ListNodenewHead =head; |
51 | | -for (inti =0;i <nums.length;i++) { |
52 | | -newHead.val =nums[i]; |
53 | | -newHead =newHead.next; |
54 | | - } |
55 | | -returnhead; |
56 | 35 | } |
57 | | - } |
58 | 36 | } |