LeetCode18|排序链表

码农王同学

发布于 2020-08-12 15:30:01

32500

代码可运行

文章被收录于专栏：后端Coder后端Coder

运行总次数：0

代码可运行

1，问题简述

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

2，示例

输入: 4->2->1->3
输出: 1->2->3->4

3，题解思路

本题基于哨兵节点加上集合排序操作


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;
    }
}