题解 | #单链表的排序#

单链表的排序

https://www.nowcoder.com/practice/f23604257af94d939848729b1a5cda08

1、根据n*logn,可考虑快排或者堆排序,但是这个链表不支持随机访问,可以考虑分治归并法

2、利用快慢指针,一个一次走一步,一个一次走俩步,走的慢的就会到达中点。进而分出俩个链表,继续递归,知道左右只有单个元素。

3、利用俩个链表的合并,我们可以把分治后的链表俩俩顺序合并,既可以得到结果。

ps:也可以考虑取巧用一个数组把链表元素装好后排序,再赋值给新的链表。

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        // write code here
        if(head == null || head.next == null){
            return head;
        }
        // 使用快慢指针寻找链表的中点
        ListNode fast = head.next, slow = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        // 慢指针到达中点
        ListNode tmp = slow.next;
        slow.next = null;
        // 递归左右俩边进行排序
        ListNode left = sortInList(head);
        ListNode right = sortInList(tmp);

        // 创建新的链表
        ListNode h = new ListNode(0);
        ListNode res = h;
        // 合并left right俩个链表
        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 ? left : right;
        return res.next;
    }
}

全部评论

相关推荐

05-14 20:34
门头沟学院 Java
窝补药贝八股:管他们,乱说,反正又不去,直接说680
点赞 评论 收藏
分享
06-15 02:05
已编辑
南昌航空大学 数据分析师
Eason三木:你如果想干技术岗,那几个发公众号合唱比赛的经历就去掉,优秀团员去掉,求职没用。然后CET4这种不是奖项,是技能,放到下面的专业技能里或者单独列一个英语能力。 另外好好改改你的排版,首行缩进完全没有必要,行间距好好调调,别让字和标题背景黏在一起,你下面说能做高质量PPT你得展现出来啊,你这简历排版我用PPT做的都能比你做的好。 然后自我评价,你如果要干数据工程师,抗压能力强最起码得有吧。
简历中的项目经历要怎么写
点赞 评论 收藏
分享
怎么起名字:早知道就不读书了,害得我送外卖还得扶眼镜
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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