public class Main { public static void main(String[] args) { ListNode head = new ListNode(1); head.next = new ListNode(100); head.next.next = new ListNode(3); head.next.next.next = new ListNode(90); head.next.next.next.next = new ListNode(5); head.next.next.next.next.next = new ListNode(1); ListNode newHead = sortList(head); printList(newHead); } public static ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode slow = head, curNode = head, fast = head; while (fast != null && fast.next != null) { slow = curNode; curNode = curNode.next; fast = fast.next.next; } // unlink slow.next = null; return mergeSort(sortList(head), sortList(curNode)); } public static ListNode mergeSort(ListNode h1, ListNode h2) { ListNode newHead = new ListNode(-1); ListNode moveNode = newHead; ListNode tmp; while (h1 != null && h2 != null) { if (h1.val < h2.val) { tmp = new ListNode(h1.val); h1 = h1.next; } else { tmp = new ListNode(h2.val); h2 = h2.next; } moveNode.next = tmp; moveNode = moveNode.next; } if (h1 != null) { moveNode.next = h1; } if (h2 != null) { moveNode.next = h2; } return newHead.next; } private static void printList(ListNode head) { String s = ""; while (head != null) { s += head.val + " "; head = head.next; } System.out.println(s); } } class ListNode { ListNode next; int val; ListNode(int val) { this.val = val; next = null; } }