1 package SortList; 2  3 import java.util.Iterator; 4  5 class ListNode { 6  7     int val; 8     ListNode next; 9     ListNode(int val) {10         this.val = val;11     }12 }13 14 public class Solution {15     public static ListNode sortList(ListNode head) {16 17         if (head == null || head.next == null) {18             return head;19         }20         /**21          * 定义两个指针，其中一个是另一个的二倍，22          * 等前一个到达链表结尾时，后一个到达链表中间23          */24         ListNode before = head.next;25         ListNode after = head;26         while (before.next != null && before.next.next != null) {27             before = before.next.next;28             after = after.next;29         }30 31         ListNode l2 = sortList(after.next);32         after.next = null;33         ListNode l1 = sortList(head);34 35         return merge(l1, l2);36 37     }38 39     static ListNode merge(ListNode list1, ListNode list2) {40 41         /**42          * 先初始化一个空链表43          * 并赋予list1和list2中的一个节点44          */45         ListNode list = null;46         if(list1.val <= list2.val){47             list = list1;48             list1 = list1.next;49         } else {50             list = list2;51             list2 = list2.next;52         }53         ListNode lis = list;54         while (list1 != null && list2 != null) {55             if (list1.val <= list2.val) {56                 lis.next = list1;57                 list1 = list1.next;58                 lis = lis.next;59             } else {60                 lis.next = list2;61                 list2 = list2.next;62                 lis = lis.next;63             }64         }65         if (list1 == null) {66             lis.next = list2;67         } else {68             lis.next = list1;69         }70         return list;71     }72 73     public static void main(String[] args) {74         ListNode list = new ListNode(73);75         ListNode list1 = new ListNode(11);76         ListNode list2 = new ListNode(25);77         ListNode list3 = new ListNode(34);78         ListNode list4 = new ListNode(18);79         list.next = list1;80         list1.next = list2;81         list2.next = list3;82         list3.next = list4;83         ListNode llll = sortList(list);84         //System.out.println(llll.next.next.val);85         while (llll != null) {86             System.out.println(llll.val);87             llll = llll.next;88         }89         // System.out.println(llll.toString());90     }91 92 }