Leetcode148.排序链表

1.题目描述

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

示例 1:

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

输入: -1->5->3->4->0
输出: -1->0->3->4->5

2.解答

首先我的想法就是每次遍历链表都找到最小节点,将其保存起来之后再将其在链表上删除,每一次遍历都找出最小节点,使用递归的方法来进行链表的重组

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null)    return head;
        //prev表示保存遍历过程中每个节点的前一个节点
        //使用temp变量对链表进行遍历
        ListNode prev = null,temp = head;
        //使用min保存每一次遍历的最小节点,初始化为头节点
        ListNode min = head;
        //保存最小节点的前一个节点,以便进行删除
        ListNode minPrev = null;
        while(temp != null){
            if(temp.val < min.val){
                min = temp;
                minPrev = prev;
            }                
            prev = temp;
            temp = temp.next;
        }
        //如果min遍历之后指向head,那么直接将head指针后移即可删除当前头节点
        if(min == head)
            head = head.next;
        else
            minPrev.next = min.next;
        //使用递归构建新的排序链表
        min.next = sortList(head);
        return min;
    }
}

这种方法只是以实现为目的,从提交记录上面来看,这个方法的性能真是惨不忍睹

我太垃圾了


在上一篇文章中复习了归并排序:归并排序

具体是使用数组实现的,动手之前觉得要求空间复杂度为常量怎么办,这一点在链表方面不用担心,在数组中实现需要创建一个新的数组用来存放排序之后的数组,在链表中只需要直接修改指针就可以了

利用递归的方法,递归的将链表分为两段,具体使用快慢指针的方法,记录下每个排序好的链表的头节点,然后使用merge进行合并

主要考察3个知识点,

  • 知识点1:归并排序的整体思想
  • 知识点2:找到一个链表的中间节点的方法
  • 知识点3:合并两个已排好序的链表为一个新的有序链表
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        return head == null ? null : mergerSort(head);
    }
    private ListNode mergerSort(ListNode head){
        if(head.next == null)   return head;
        ListNode p1 = head,p2 = head,prev = null;
        while(p2 != null && p2.next != null){
            prev = p1;
            p1 = p1.next;
            p2 = p2.next.next;
        }
        prev.next = null;
        ListNode l = mergerSort(head);
        ListNode r = mergerSort(p1);
        return merge(l,r);
    }
    private ListNode merge(ListNode l,ListNode r){
        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;
        while(l != null && r != null){
            if(l.val <= r.val){
                cur.next = l;
                cur = cur.next;
                l = l.next;
            }
            else{
                cur.next = r;
                cur = cur.next;
                r = r.next;
            }
        }
        if(l != null)
            cur.next = l;
        if(r != null)
            cur.next = r;
        return dummyHead.next;
    }
}

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://hadoo666.top/archives/leetcode148排序链表md