侧边栏壁纸
博主头像
惊羽博主等级

hi ,我是惊羽,前生物学逃兵,现系统工程沉迷者 . 贝壳签约工程师 , 曾被雇佣为 联拓数科 · 支付研发工程师 、京东 · 京东数科 · 研发工程师、中国移动 · 雄安产业研究院 · 业务中台技术负责人 .

  • 累计撰写 100 篇文章
  • 累计创建 14 个标签
  • 累计收到 9 条评论

算法练习(3) - 链表排序

惊羽
2021-06-16 / 0 评论 / 0 点赞 / 145 阅读 / 1,382 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2021-11-05,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。
package top.buukle.buukle.排序类;

public class 排序链表 {

    //给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。
//
// 进阶:
//
//
// 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?
//
//
//
//
// 示例 1:
//
//
//输入:head = [4,2,1,3]
//输出:[1,2,3,4]
//
//
// 示例 2:
//
//
//输入:head = [-1,5,3,4,0]
//输出:[-1,0,3,4,5]
//
//
// 示例 3:
//
//
//输入:head = []
//输出:[]
//
//
//
//
// 提示:
//
//
// 链表中节点的数目在范围 [0, 5 * 104] 内
// -105 <= Node.val <= 105
//
// Related Topics 排序 链表
// 👍 1179 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */

 public class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }
    class Solution {
        public ListNode sortList(ListNode head) {
            if(head == null || head.next == null){
                return head;
            }
            // 找到中心节点
            ListNode slow = head;
            ListNode fast = head.next;

            while(fast != null && fast.next != null){
                slow = slow.next;
                fast = fast.next.next;
            }
            // 初始化后半截儿
            ListNode after =  slow.next;
            // 切断链表
            slow.next = null ;
            // 递归调用并排序
            ListNode left = sortList(head);
            ListNode right = sortList(after);

            ListNode res = new ListNode();
            ListNode h = res;

            while(left != null && right != null){
                if(left.val < right.val){
                    h.next = left;
                    left = left.next;
                }else{
                    h.next = right;
                    right = right.next;
                }
                h = h.next;
            }
            h.next = left == null ? right : left;
            return res.next;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}

0
广告 广告

评论区