LeetCode---hot100---排序链表

                                               排序链表

题目

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

 

示例 1:

 

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

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

示例 2:

 

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

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

思路

 

 

 

代码

public static void main(String[] args) {
        ListNode n1 = new ListNode(4);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(1);
        ListNode n4 = new ListNode(3);

        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        sortList(n1);
    }
    public static ListNode sortList(ListNode head) {
        if(head == null){
            return head;
        }
        return mergeSort(head);
    }

    /**
     * @Author liuhaidong
     * @Description 递归分解序列为两个子序列,并向上并归排序
     *               使用快慢指针法,快指针到终点时慢指针指向中点
     * @param
     * @Date 16:21 2020/1/3 0003
     */
    private static ListNode mergeSort(ListNode head) {
        if(head.next == null){
            return head;
        }
        //快指针,考虑到链表为2时的情况,fast比slow早一格
        ListNode fast = head.next;
        //慢指针
        ListNode slow = head;
        //快慢指针开跑
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //找到右子链表头元素,复用fast引用
        fast = slow.next;
        //将中点后续置空,切割为两个子链表
        slow.next = null;
        //递归分解左子链表,得到新链表起点
        head = mergeSort(head);
        //递归分解右子链表,得到新链表起点
        fast=mergeSort(fast);
        //并归两个子链表
        ListNode newHead = merge(head,fast);
        return newHead;
    }

    /**
     * @Author liuhaidong
     * @Description 以left节点为起点的左子序列 及 以right为起点的右子序列
     *               并归为一个有序序列并返回头元素;
     * @param
     * @Date 16:26 2020/1/3 0003
     */
    private static ListNode merge(ListNode left, ListNode right) {
        //维护临时序列的头元素
        ListNode head;
        if (left.val<= right.val) {
            head = left;
            left = left.next;
        } else {
            head = right;
            right = right.next;
        }
        //两个子链表均存在剩余元素
        ListNode temp = head;
        while (left != null && right != null){
            //将较小的元素加入临时序列
            if (left.val <= right.val) {
                temp.next=left;
                left = left.next;
                temp = temp.next;
            } else {
                temp.next=right;
                right = right.next;
                temp = temp.next;
            }
        }
        //左子序列用完将右子序列余下元素加入临时序列
        if (left == null) {
            temp.next=right;
        }
        //右子序列用完将左子序列余下元素加入临时序列
        if (right == null) {
            temp.next=left;
        }
        return head;
    }

 

public class ListNode {
    int val;
    // 保存链表的值
    ListNode next;
    // 下一个结点
    ListNode(int x) {
        val = x; }
}

全部评论

相关推荐

Hakasee:我的简历和你的基本一样,上周去了上海,boss投了三百家, 三家线下面试 第一家没有做题,全是八股和项目,因为第一次面试不怎么熟练,挂了 第二家,给你几个题目(①css垂直居中文字,字体每两秒闪烁一下以及点击弹窗,②给你一个链接,实现可视化地图,③然后是八股,图片性能优化,以及对图片app有什么想法),45分钟内做完,然后老板面试) 第三家特别偏僻,有点阴森,到了之后让了一个工位给我,有四个题目,①格式化时间 年月日当前时间星期几② 正则表达式提取新闻文字,③在文本域输入文字生成选择题以及选项④生成商品排版还是什么来着 三家都是不超过50人的小公司 两家线上牛客笔试(卡伦特,七牛云,但是笔试不仅要考前端,还要考后端,算法,甚至数学题 我的建议是如果只做了这两个vue项目且不怎么熟练的情况下,先沉淀沉淀,把react学了,上海好的公司基本都是react查看图片
点赞 评论 收藏
分享
07-17 12:14
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务