1，问题简述
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
2，示例
代码语言：javascript复制输入: 4->2->1->3
输出: 1->2->3->43，题解思路
本题基于哨兵节点加上集合排序操作
代码语言：javascript复制
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class SortListTest {
public static void main(String[] args) {
ListNode l1 = new ListNode(4);
ListNode l2 = new ListNode(2);
ListNode l3 = new ListNode(1);
ListNode l4 = new ListNode(3);
l1.next = l2;
l2.next = l3;
l3.next = l4;
ListNode listNode = sortList(l1);
System.out.println("listNode = " listNode);
System.out.println("------------------------------");
ListNode l21 = new ListNode(-1);
ListNode l22 = new ListNode(5);
ListNode l23 = new ListNode(3);
ListNode l24 = new ListNode(4);
ListNode l25 = new ListNode(0);
l21.next = l22;
l22.next = l23;
l23.next = l24;
l24.next = l25;
ListNode listNode1 = sortList(l21);
System.out.println("listNode1 = " listNode1);
}
public static ListNode sortList(ListNode head) {
if (head == null) {
return head;
}
List<Integer> list = new ArrayList<>();
ListNode tempNode = head;
while (tempNode != null) {
list.add(tempNode.val);
tempNode = tempNode.next;
}
Collections.sort(list);
ListNode dummyNode = new ListNode(-1);
ListNode temp = dummyNode;
for (Integer num : list
) {
temp.next = new ListNode(num);
temp = temp.next;
}
return dummyNode.next;
}
}
