题解 | #单链表的排序#

单链表的排序

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

public class Solution {
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        // write code here
        List<ListNode> lists = new ArrayList<>();
        while (head != null) {
            ListNode next = head.next;
            head.next = null;
            lists.add(head);
            head = next;
        }
        while (lists.size() > 1) {
            if (lists.size() % 2 == 0) {
                List<ListNode> cur = new ArrayList<>();
                for (int i = 1 ; i < lists.size() ; i += 2) {
                   cur.add(mergeSort(lists.get(i-1),lists.get(i)));
                }
                lists = cur;
            } else {
                List<ListNode> cur = new ArrayList<>();
                for (int i = 1 ; i < lists.size() - 1; i += 2) {
                   cur.add(mergeSort(lists.get(i-1),lists.get(i)));
                }
                cur.add(lists.get(lists.size() - 1));
                lists = cur;
            }
        }
        return lists.get(0);
    }
    public ListNode mergeSort(ListNode root1,ListNode root2) {
        ListNode vHead = new ListNode(-100);
        ListNode work = vHead;
        work.next = null;
        while (root1 != null && root2 != null) {
            if (root1.val < root2.val) {
                work.next = root1;
                work = work.next;
                root1 = root1.next;
            } else {
                work.next = root2;
                work = work.next;
                root2 = root2.next;
            }
        }
        while (root1 != null) {
            work.next = root1;
            work = work.next;
            root1 = root1.next;
        }
         while (root2 != null) {
            work.next = root2;
            work = work.next;
            root2 = root2.next;
        }
        return vHead.next;
    }
}


// 归并排序的想法

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-02 18:35
简历上把1个月实习写成了3个月,会进行背调吗?
码农索隆:一个月有一个月的实习经历,三个月有三个月的实习经历
简历当中有水分算不算造假...
点赞 评论 收藏
分享
06-07 19:59
门头沟学院 C++
补药卡我啊😭:都快15年前的了还在11新特性
你的简历改到第几版了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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