1+ package Algorithms .sort ;
2+
3+ import Algorithms .algorithm .others .ListNode ;
4+
5+ /**
6+ * Definition for singly-linked list.
7+ * class ListNode {
8+ * int val;
9+ * ListNode next;
10+ * ListNode(int x) {
11+ * val = x;
12+ * next = null;
13+ * }
14+ * }
15+ */
16+ public class SortList {
17+ public static void main (String []strs ) {
18+ ListNode n1 =new ListNode (2 );
19+ ListNode n2 =new ListNode (18 );
20+ ListNode n3 =new ListNode (3 );
21+ ListNode n4 =new ListNode (54 );
22+ ListNode n5 =new ListNode (6 );
23+ ListNode n6 =new ListNode (90 );
24+ ListNode n7 =new ListNode (2 );
25+ ListNode n8 =new ListNode (1 );
26+ ListNode n9 =new ListNode (19 );
27+ ListNode n10 =new ListNode (30 );
28+
29+
30+ n1 .next =n2 ;
31+ n2 .next =n3 ;
32+ n3 .next =n4 ;
33+ n4 .next =n5 ;
34+ n5 .next =n6 ;
35+ n6 .next =n7 ;
36+ n7 .next =n8 ;
37+ n8 .next =n9 ;
38+ n9 .next =n10 ;
39+ n10 .next =null ;
40+
41+ ListNode ret =sortList (n1 );
42+ System .out .println (ret .toString ());
43+ }
44+
45+ public static ListNode sortList1 (ListNode head ) {
46+ // Nodes should be more than 2.
47+ if (head ==null ||head .next ==null ) {
48+ return head ;
49+ }
50+
51+ // get the mid node.
52+ ListNode midPre =getMidPre (head );
53+
54+ // Cut the two list.
55+ ListNode right =midPre .next ;
56+ midPre .next =null ;
57+
58+ // Sort the left side and the right side.
59+ ListNode left =sortList (head );
60+ right =sortList (right );
61+
62+ // Merge the two sides together.
63+ return merge (left ,right );
64+ }
65+
66+ // get the pre node before mid.
67+ public static ListNode getMidPre1 (ListNode head ) {
68+ ListNode slow =head ;
69+ ListNode fast =head ;
70+
71+ while (fast !=null &&fast .next !=null &&fast .next .next !=null ) {
72+ slow =slow .next ;
73+ fast =fast .next .next ;
74+ }
75+
76+ return slow ;
77+ }
78+
79+ // get the pre node before mid.
80+ public static ListNode getMidPre (ListNode head ) {
81+ ListNode slow =head ;
82+
83+ // fast提前一点儿。这样就可以得到前一个节点喽。
84+ ListNode fast =head .next ;
85+
86+ while (fast !=null &&fast .next !=null ) {
87+ slow =slow .next ;
88+ fast =fast .next .next ;
89+ }
90+
91+ return slow ;
92+ }
93+
94+ public static ListNode merge (ListNode head1 ,ListNode head2 ) {
95+ ListNode dummy =new ListNode (0 );
96+ ListNode cur =dummy ;
97+
98+ while (head1 !=null &&head2 !=null ) {
99+ if (head1 .val <head2 .val ) {
100+ cur .next =head1 ;
101+ head1 =head1 .next ;
102+ }else {
103+ cur .next =head2 ;
104+ head2 =head2 .next ;
105+ }
106+
107+ cur =cur .next ;
108+ }
109+
110+ if (head1 !=null ) {
111+ cur .next =head1 ;
112+ }else {
113+ cur .next =head2 ;
114+ }
115+
116+ return dummy .next ;
117+ }
118+
119+ /*
120+ The Solution 2:
121+ Quick Sort.
122+ */
123+ public static ListNode sortList (ListNode head ) {
124+ if (head ==null ) {
125+ return null ;
126+ }
127+
128+ // Sort the list from 0 to len - 1
129+ return quickSort (head );
130+ }
131+
132+ // The quick sort algorithm
133+
134+ // All the elements are the same!
135+ public static boolean isDuplicate (ListNode head ) {
136+ while (head !=null ) {
137+ if (head .next !=null &&head .next .val !=head .val ) {
138+ return false ;
139+ }
140+
141+ head =head .next ;
142+ }
143+
144+ return true ;
145+ }
146+
147+ public static ListNode quickSort (ListNode head ) {
148+ if (head ==null ) {
149+ return null ;
150+ }
151+
152+ // 如果整个链是重复的，直接跳过。
153+ if (isDuplicate (head )) {
154+ return head ;
155+ }
156+
157+ // Use the head node to be the pivot.
158+ ListNode headNew =partition (head ,head .val );
159+
160+ // Find the pre position of the pivoit.
161+ ListNode cur =headNew ;
162+
163+ ListNode dummy =new ListNode (0 );
164+ dummy .next =headNew ;
165+
166+ ListNode pre =dummy ;
167+
168+ // Find the pre node and the position of the piviot.
169+ while (cur !=null ) {
170+ if (cur .val ==head .val ) {
171+ break ;
172+ }
173+
174+ // move forward.
175+ cur =cur .next ;
176+ pre =pre .next ;
177+ }
178+
179+ // Cut the link to be three parts.
180+ pre .next =null ;
181+
182+ // Get the left link;
183+ ListNode left =dummy .next ;
184+
185+ // Get the right link.
186+ ListNode right =cur .next ;
187+ cur .next =null ;
188+
189+ // Recurtion to call quick sort to sort left and right link.
190+ left =quickSort (left );
191+ right =quickSort (right );
192+
193+ // Link the three part together.
194+
195+ // Link the first part and the 2nd part.
196+ if (left !=null ) {
197+ dummy .next =left ;
198+
199+ // Find the tail of the left link.
200+ while (left .next !=null ) {
201+ left =left .next ;
202+ }
203+ left .next =cur ;
204+ }else {
205+ dummy .next =cur ;
206+ }
207+
208+ cur .next =right ;
209+
210+ // The new head;
211+ return dummy .next ;
212+ }
213+
214+ // Return the new head;
215+ public ListNode partition (ListNode head ,int x ) {
216+ if (head ==null ) {
217+ return null ;
218+ }
219+
220+ ListNode dummy =new ListNode (0 );
221+ dummy .next =head ;
222+
223+ ListNode pre =dummy ;
224+ ListNode cur =head ;
225+
226+ // Record the big list.
227+ ListNode bigDummy =new ListNode (0 );
228+ ListNode bigTail =bigDummy ;
229+
230+ while (cur !=null ) {
231+ if (cur .val >=x ) {
232+ // Unlink the cur;
233+ pre .next =cur .next ;
234+
235+ // Add the cur to the tail of the new link.
236+ bigTail .next =cur ;
237+ cur .next =null ;
238+
239+ // Refresh the bigTail.
240+ bigTail =cur ;
241+
242+ // 移除了一个元素的时候，pre不需要修改，因为cur已经移动到下一个位置了。
243+ }else {
244+ pre =pre .next ;
245+ }
246+
247+ cur =pre .next ;
248+ }
249+
250+ // Link the Big linklist to the smaller one.
251+ pre .next =bigDummy .next ;
252+
253+ return dummy .next ;
254+ }
255+ }