【每日一题】【归并排序/堆排序&虚拟头结点】148. 排序链表-211220/220217【出栈时不断容易产生环状链表！】

给你链表的头结点 head ，请将其按升序排列并返回排序后的链表。

进阶：

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

方法1：归并排序+使用辅助函数

import java.util.*;

/*

 * public class ListNode {

 *   int val;

 *   ListNode next = null;

 * }

 */

public class Solution {

    /**

     *

     * @param head ListNode类 the head node

     * @return ListNode类

     */

    public ListNode sortInList (ListNode head) {

        return head == null ? null : mergeSort(head);

    }

    public ListNode mergeSort(ListNode head) {

        if(head.next == null) {

            return head;

        }

        ListNode slow = head, fast = head;

        //需要断开两个链表！！！

        ListNode pre = null;

        //注意：fast指针判断时要分别判断

        while(fast != null && fast.next != null) {

            pre = slow;

            slow = slow.next;

            fast = fast.next.next;

        }

        pre.next = null; //将链表分成两部分，才能分别递归计算

        ListNode left = mergeSort(head);

        ListNode right = mergeSort(slow);

        return merge(left, right);

    }

    public ListNode merge(ListNode left, ListNode right) {

        ListNode dummy = new ListNode(-1);

        ListNode cur = dummy;

        while(left != null && right != null) {

            if(left.val < right.val) {

                cur.next = left;

                cur = cur.next;

                left = left.next;

            } else {

                cur.next = right;

                cur = cur.next;

                right = right.next;

            }

        }

        if(left != null) {

            cur.next = left;

        }

        if(right != null) {

            cur.next = right;

        }

        return dummy.next;

    }

}

方法2：堆排序&确定虚拟节点

import java.util.*;

/*

 * public class ListNode {

 *   int val;

 *   ListNode next = null;

 * }

 */

public class Solution {

    /**

     *

     * @param head ListNode类 the head node

     * @return ListNode类

     */

    //会超时

    public ListNode sortInList (ListNode head) {

        PriorityQueue<ListNode> queue = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);

        while(head != null) {

            queue.offer(head);

            head = head.next;

        }

        //虚拟节点与cur节点的确定

        ListNode dummy = new ListNode(-1);

        ListNode cur = queue.poll();

        dummy.next = cur;

        while(!queue.isEmpty()) {

            cur.next = queue.poll();

            cur = cur.next;

        }
　　　　 cur.next = null; //入队时next指针存着下一个元素，要断掉指针指向，否则会产生超时（环形链表）

        return dummy.next;

    }

}

如何确定虚拟头结点和cur节点之间的关系？

前提：head不为空

ListNode dummy = new ListNode(-1);

dummy.next = head;

ListNode cur = dummy.next;

ListNode pre = dummy;

方法3：使用Collections集合工具类排序

新建节点并返回

import java.util.*;

/*

 * public class ListNode {

 *   int val;

 *   ListNode next = null;

 * }

 */

public class Solution {

    /**

     *

     * @param head ListNode类 the head node

     * @return ListNode类

     */

    //方法3：ArrayList存值后，使用工具类排序，建新节点

    public ListNode sortInList (ListNode head) {

        if(head == null || head.next == null) {

            return head;

        }

        ListNode cur = new ListNode(0);

        ArrayList<Integer> list = new ArrayList<>();

        while(head != null) {

            list.add(head.val);

            head = head.next;

        }

        Collections.sort(list);

        ListNode p = cur;

        for(int i = 0; i < list.size(); i++) {

            ListNode node = new ListNode(list.get(i));

            p.next = node;

            p = p.next;

        }

        return cur.next;

    }

}

巴特西

【每日一题】【归并排序/堆排序&虚拟头结点】148. 排序链表-211220/220217【出栈时不断容易产生环状链表！】

最新文章

热门文章