1+ package Algorithms .list ;
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 ListNode sortList (ListNode head ) {
18+ // Nodes should be more than 2.
19+ if (head ==null ||head .next ==null ) {
20+ return head ;
21+ }
22+
23+ // get the mid node.
24+ ListNode midPre =getMidPre (head );
25+
26+ // Cut the two list.
27+ ListNode right =midPre .next ;
28+ midPre .next =null ;
29+
30+ // Sort the left side and the right side.
31+ ListNode left =sortList (head );
32+ right =sortList (right );
33+
34+ // Merge the two sides together.
35+ return merge (left ,right );
36+ }
37+
38+ // get the pre node before mid.
39+ public ListNode getMidPre1 (ListNode head ) {
40+ ListNode slow =head ;
41+ ListNode fast =head ;
42+
43+ while (fast !=null &&fast .next !=null &&fast .next .next !=null ) {
44+ slow =slow .next ;
45+ fast =fast .next .next ;
46+ }
47+
48+ return slow ;
49+ }
50+
51+ // get the pre node before mid.
52+ public ListNode getMidPre (ListNode head ) {
53+ ListNode slow =head ;
54+
55+ // fast提前一点儿。这样就可以得到前一个节点喽。
56+ ListNode fast =head .next ;
57+
58+ while (fast !=null &&fast .next !=null ) {
59+ slow =slow .next ;
60+ fast =fast .next .next ;
61+ }
62+
63+ return slow ;
64+ }
65+
66+ public ListNode merge (ListNode head1 ,ListNode head2 ) {
67+ ListNode dummy =new ListNode (0 );
68+ ListNode cur =dummy ;
69+
70+ while (head1 !=null &&head2 !=null ) {
71+ if (head1 .val <head2 .val ) {
72+ cur .next =head1 ;
73+ head1 =head1 .next ;
74+ }else {
75+ cur .next =head2 ;
76+ head2 =head2 .next ;
77+ }
78+
79+ cur =cur .next ;
80+ }
81+
82+ if (head1 !=null ) {
83+ cur .next =head1 ;
84+ }else {
85+ cur .next =head2 ;
86+ }
87+
88+ return dummy .next ;
89+ }
90+ }