题解 | #单链表的排序#

单链表的排序

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

using System;
using System.Collections.Generic;

/*
public class ListNode
{
    public int val;
    public ListNode next;

    public ListNode (int x)
    {
        val = x;
    }
}
*/

class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public static ListNode Merge(ListNode head1, ListNode head2) {
        if (head1 == null) return head2;
        if (head2 == null) return head1;
        ListNode res = new ListNode(-1);
        ListNode tail = res;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                tail.next = head1;
                tail = head1;
                head1 = head1.next;
            } else {
                tail.next = head2;
                tail = head2;
                head2 = head2.next;
            }
        }
        tail.next = head1 == null ? head2 : head1;
        return res.next;
    }
    public ListNode sortInList(ListNode head) {
        // write code here
        if (head == null || head.next == null) return head;
        ListNode left = head;
        ListNode mid = head.next;
        ListNode right = head.next.next;
        while (right != null && right.next != null) {
            left = left.next;
            mid = mid.next;
            right = right.next.next;
        }
        left.next = null;
        return Merge(sortInList(head), sortInList(mid));
    }
}

全部评论

相关推荐

昨天 11:08
门头沟学院 Java
投递京东等公司9个岗位
点赞 评论 收藏
分享
05-19 19:57
蚌埠学院 Python
2237:Gpa70不算高,建议只写排名,个人技能不在多而在精,缩到8条以内。项目留一个含金量高的,减少间距弄到一页,硕士简历也就一页,本科不要写很多
实习,投递多份简历没人回...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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