链表排序__牛客网

Java

FARO_Z

WC137 单链表排序是 easy，这里的单链表就是 hard 了，离谱...

public ListNode sortList (ListNode head) {
        if (head==null || head.next==null) return head;
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast!=null && fast.next!=null) {
            fast=fast.next.next;
            slow=slow.next;
        }
        // 获取链表的两个部分
        ListNode h1 = head;
        ListNode h2 = slow.next;
        slow.next=null;

        // 对两个部分递归进行归并排序
        h1 = sortList(h1);
        h2 = sortList(h2);

        // 归并有序链表
        return merge(h1,h2);
    }

    public ListNode merge(ListNode h1,ListNode h2) {
        ListNode head = new ListNode(-1);
        ListNode tail = head;
        while (h1!=null && h2!=null) {
            if (h1.val<=h2.val) {
                tail.next=h1;
                tail=tail.next;
                h1=h1.next;
            } else {
                tail.next=h2;
                tail=tail.next;
                h2=h2.next;
            }
        }
        tail.next=h1!=null?h1:h2;
        return head.next;
    }

发表于 2021-10-11 10:52:46 回复(0)

Java

LiberHome

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode sortList (ListNode head) {
        // write code here
        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 tmp = slow.next;
        slow.next = null;
        
        ListNode left = sortList(head);
        ListNode right = sortList(tmp);
        ListNode h = new ListNode(0);
        ListNode res = h;
        
        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;
    }
}

发表于 2020-10-24 21:39:48 回复(0)

Java

Kinggj

利用归并排序；依次递归：1）找到中间节点 2）左右分支各自排序 3）合并两个有序链表

import java.util.*;
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */
public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode sortList (ListNode head) {
        // write code here
        if(head==null || head.next==null) return head;
        ListNode mid = findMidList(head);
        //断开
        ListNode midNext = mid.next;
        mid.next=null;
        return mergeList(sortList(head),sortList(midNext));
    }
    public ListNode findMidList(ListNode h){
        if(h==null || h.next==null) return h;
        ListNode l1 =h;
        ListNode l2 =h;
        while(l2.next!=null && l2.next.next!=null){
            l1=l1.next;
            l2=l2.next.next;
        }
        return l1;
    }
    public ListNode mergeList(ListNode left,ListNode right){
        ListNode head ,relist;//结果
        if(left==null)return right;
        if(right==null)return left;
        ListNode f1=left.next,f2=right.next;
        //头结点判断
        if(left.val<right.val){
            relist=head=left;
            f2=right;
        }else{
            relist=head=right;
            f1=left;
        }
        while(f1!=null && f2 !=null){
            if(f1.val<f2.val){
                relist.next=f1;
                relist=relist.next;
                f1 = f1.next;
            }else{
                relist.next=f2;
                relist=relist.next;
                f2 = f2.next;
            }
        }
        if(f1!=null){
             relist.next=f1;
        }
        if(f2!=null){
             relist.next=f2;
        }
        return head;
    }
}

发表于 2020-08-19 19:24:14 回复(0)

Java

灯丰

public ListNode sortList (ListNode head) {
// write code here
        ListNode ret = head;

        for (ListNode p,l, n = head; n != null;) {
            p = n;
            // ListNode target = add(new ListNode(p.val),n);
            l = p.next;
            p.next = null;
            if(n == head){
                ret.next = null;
            }
            n=l;
            ret = add(ret, p);
        }
        return ret;
}

//排序

public ListNode add(ListNode target,ListNode p){
ListNode ret = target;
if(target == null){
throw new RuntimeException("ille");
}
if(p == null || p == target){
return target;
}

if(target.val > p.val){
    ret = left(target, p);
}else{
    ret = right(target, p);
}

return ret;
}

public ListNode right(ListNode target,ListNode p){
    ListNode n,ret = null;

    if(target.val<p.val){
        if((n=target.next) == null){
            target.next = p;
        ret = target;
        }
        else{
            ret = right(n, p);
        if(target != ret && n != ret){
            //n.next = ret;
            target.next = ret;
        }
        ret = target;
        }

    }else{
        ret = left(target,p);
    }
    return ret;
}

public ListNode left(ListNode target,ListNode p){
    ListNode n,ret = null;

    p.next = target;
    ret = p;

    return ret;
}

发表于 2020-06-06 20:13:31 回复(0)

Java

I_Mars

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode sortList(ListNode head) {
        if(head==null||head.next==null)
            return head;
        ListNode mid=findmid(head);
        ListNode right=mid.next;
        mid.next=null;
        return merge(sortList(head),sortList(right));
    }
    public ListNode findmid(ListNode head){
        if(head==null||head.next==null)
            return head;
        ListNode fast,slow;
        fast=slow=head;
        while(fast.next!=null&&fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
    public ListNode merge(ListNode left,ListNode right){
        if(left==null)
            return right;
        if(right==null)
            return left;
        ListNode head,t;
        if(left.val<right.val){
            t=left;
            head=t;
            left=left.next;
        }
        else{
            t=right;
            head=t;
            right=right.next;
        }
        while(left!=null&&right!=null){
            if(left.val<right.val){
                t.next=left;
                left=left.next;
                t=t.next;
            }
            else{
                t.next=right;
                right=right.next;
                t=t.next;
            }
        }
        if(left==null){
            t.next=right;
        }
        if(right==null){
            t.next=left;
        }
        return head;
    }
}

发表于 2020-02-21 13:26:00 回复(0)

Java

AriesLi

回顾一下常见排序算法及其时间复杂度，空间复杂度：

图片来源: https://www.cnblogs.com/hokky/p/8529042.html

可以看出满足条件的只有堆排序以及归并排序，其他解析归并排序居多，我这里复习和使用堆排序方法。

复习一下堆排序相关知识：

1. 定义

什么叫做堆？

满足：1）堆中任意节点的值总是不大于(不小于)其子节点的值；
2) 堆总是一棵完全树。

常见的堆有二叉堆、左倾堆、斜堆、二项堆、斐波那契堆等等。

二叉堆是完全二叉树或者是近似完全二叉树，它分为两种：
最大堆：父结点的键值总是大于或等于任何一个子节点的键值；

最小堆：父结点的键值总是小于或等于任何一个子节点的键值。

那什么叫做完全二叉树(Complete Tree)?

完全二叉树：除了最后一层之外的其他每一层都被完全填充，并且所有结点都保持向左对齐。

满二叉树：除了叶子结点之外的每一个结点都有两个孩子，每一层(当然包含最后一层)都被完全填充。

完满二叉树：除了叶子结点之外的每一个结点都有两个孩子结点。

我们将任意节点不大于其子节点的堆叫做最小堆或小根堆，而将任意节点不小于其子节点的堆叫做最大堆或大根堆。最大堆通常被用来进行"升序"排序，而最小堆通常被用来进行"降序"排序。

二叉堆一般都通过"数组"来实现。数组实现的二叉堆，父节点和子节点的位置存在一定的关系。有时候，我们将"二叉堆的第一个元素"放在数组索引0的位置，有时候放在1的位置。当然，它们的本质一样(都是二叉堆)，只是实现上稍微有一丁点区别。
假设"第一个元素"在数组中的索引为 0 的话，则父节点和子节点的位置关系如下：
(01) 索引为i的左孩子的索引是 (2*i+1);
(02) 索引为i的左孩子的索引是 (2*i+2);
(03) 索引为i的父结点的索引是 floor((i-1)/2);

3. 堆排序的思路

1）初始化堆：将数列a[1...n]构造成最大堆。
2）交换数据：将a[1]和a[n]交换，使a[n]是a[1...n]中的最大值；然后将a[1...n-1]重新调整为最大堆。接着，将a[1]和a[n-1]交换，使a[n-1]是a[1...n-1]中的最大值；然后将a[1...n-2]重新调整为最大值。依次类推，直到整个数列都是有序的。

以上概括源自

https://www.cnblogs.com/skywang12345/p/3610187.html https://www.cnblogs.com/skywang12345/p/3602162.html

有时间可以仔细看一下。

所以思路就很清晰了，我们需要一个数列来实现一个二叉堆，然后完成初始化方法和堆的调整方法。

初始化方法也依赖于堆的调整方法，

下面上代码：

public class Solution {


    private static void swap(ListNode a, ListNode b) {
        int tmp = a.val;
        a.val = b.val;
        b.val = tmp;
    }

    private static int len(ListNode head) {
        int n = 0;
        while(head!=null){
            n++;
            head = head.next;
        }
        return n;
    }

    class MaxHeap {

       ListNode[] heap;
       private int length;

       MaxHeap(ListNode head){
           length = len(head);
           heap = new ListNode[length];
           int i = 0;
           while (head!=null){
               heap[i++] = head;
               head = head.next;
           }
           adjust();
       }

       // 从start节点开始，通过“下沉”来调整堆，如果一旦下移节点，换下去的节点就可能被破坏子节点最大堆性质，需要继续调整。
       private void adjNodeDown(int start, int end){
           ListNode curNode = heap[start];
           int next = 2*start+1;
           while (next <= end) {
               if (next+1 <= end && heap[next+1].val > heap[next].val) {
                   next++;
               }
               if (curNode.val >= heap[next].val) {
                   break;
               } else {
                   swap(curNode, heap[next]);
                   curNode = heap[next];
                   next = 2*next +1;
               }
           }
       }

       // 调整二叉堆为最大堆
       private void adjust(){
           if(length<2) return;
                      //从最后一个非叶子节点开始遍历，通过子节点对应父节点是floor((i-1)/2)推导得来
                      //从叶子节点开始遍历也可以，如果没有叶子节点就跳过去 int start = (length-2)/2;
           while (start >= 0){
               adjNodeDown(start--, length-1);
           }
       }

       // 递增排序，依赖最大堆性质，每次取出根节点(最大值)往数组后面放，缩小堆大小并重新调整，获取新的最大值
       ListNode sortAsc(){
           int i = length-1;
           while (i>0){
               swap(heap[0], heap[i]);
               adjNodeDown(0, --i);
           }
           return heap[0];
       }

    }

    public ListNode sortList(ListNode head) {
        if(head==null) return null;
        MaxHeap maxHeap = new MaxHeap(head);
        return maxHeap.sortAsc();
    }
}

编辑于 2019-12-27 00:39:00 回复(0)

Java

Mono_Chrome

public class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null) {
            return null;
        }
        return mergeSort(head);
    }

    public ListNode mergeSort(ListNode head) {
        if (head.next == null) {
            return head;
        }
        ListNode pre = null;
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null;
        ListNode l1 = mergeSort(head);
        ListNode l2 = mergeSort(slow);
        return merge(l1, l2);
    }

    public ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                cur = cur.next;
                l1 = l1.next;
            } else {
                cur.next = l2;
                cur = cur.next;
                l2 = l2.next;
            }
        }
        if (l1 != null) {
            cur.next = l1;
        }
        if (l2 != null) {
            cur.next = l2;
        }
        return dummy.next;
    }
}

发表于 2019-11-05 18:45:32 回复(0)

Java

相信自己的信念

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null)return null;
        else return mergeSort(head);
    }
    public ListNode mergeSort(ListNode head){  
        if(head == null || head.next == null){
            return head;
        }
        ListNode fast = head;
        ListNode slow = head;
        ListNode pre = null;
        while(fast!=null && fast.next != null){  // 划分 O(n)
            fast = fast.next.next;
            pre = slow;
            slow = slow.next;
        }
        if(slow != fast){
            pre.next = null;
        }
        ListNode left = head;
        ListNode right = slow;

        ListNode l = mergeSort(left);  //递归求解左半部分 T(n/2)
        ListNode r = mergeSort(right);  // 递归求解右半部分 T(n/2)

        return merge(l,r);
    }
    public  ListNode merge(ListNode left, ListNode right){ //有序单链表的归并，空间复杂度O(1)
        if(left == null){
            return right;
        }
        if(right == null){
            return left;
        }
        ListNode resHead = null; // resHead 新生成链表的表头
        ListNode res = null;  // res 跟踪新链表尾端
        if(left.val>right.val){
            resHead = right;
            right = right.next;
        }else {
            resHead = left;
            left = left.next;
        }
        res = resHead;
        while(right!=null && left!=null){
            if(left.val<right.val){
                res.next = left;
                left = left.next;
            }else {
                res.next = right;
                right = right.next;
            }
            res = res.next;
        }
        if(left!=null){
            res.next = left;
        }
        if(right!=null){
            res.next = right;
        }
        return resHead;
    }
}

发表于 2019-08-16 11:53:26 回复(0)

Java

放生(^o^)/~

public class Solution {
   public ListNode sortList(ListNode head) {
         if (head==null) return null;
         return fen( head );
    }
    public ListNode bing(ListNode start,ListNode left)
    {
        ListNode s = start;
        ListNode l = left;
        ListNode node = null;
        while(start!=null && left!=null)
        {
            if(start.val<=left.val) {
                if(node!=null) node.next = start;
                node = start;
                start = start.next;
            }else{
                if(node!=null) node.next = left;
                node = left;
                left = left.next;
            }
        }
        if(start==null) node.next=left;
        if(left==null) node.next=start;
        if (s.val<=l.val)  return s;
        return l;
    }
    public ListNode fen(ListNode node)
    {
        if(node.next==null) return node;
        ListNode root = node.next;
        node.next = null;
        ListNode q = bing( node,fen( root ) );
        return q;
    }
}

我也不知道我的答案满不满足题意，反正我过了，嘿嘿

发表于 2019-07-17 14:55:23 回复(0)

Java

字节研发工程师

package LinkedList;

//本题涉及的知识点：
// 1.链表的定义；
// 2.构归并排序的sort和merge函数的实现；
// 3.链表的指针操作，
// 4.合并两个有序链表
public class SortList {
    class ListNode{//链表节点的定义
        int val;
        ListNode next;
        ListNode(int x){
            this.val = x;
            this.next = null;
        }//带一个参数的构造函数
    }

    public ListNode sortList(ListNode head) {
        //框架：1：自上而下的归并写法。   sort(a,low,mid);sort(a,mid+1,high);merge(a,low,mid,high);
        if (head==null||head.next==null)
            return head;
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next!=null&&fast.next.next!=null){
            if (head==null || head.next==null){
                slow = head;
                break;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode mid = slow;

        //这里要断开链接，分两步：先获取后一个节点，然后将前一个节点的下一个节点指向空
        ListNode midNext = mid.next;//获取后一个节点，作为后半部分的头结点
        mid.next = null;//指向空
        ListNode left = sortList(head);
        ListNode right = sortList(midNext);
        return merge(left,right);
    }

    //归并操作，将两个有序的链表合并在一起
    private ListNode merge(ListNode left, ListNode right) {
        if (left==null)
            return right;
        if (right==null)
            return left;
        ListNode retNode = null;
        ListNode curNode = null;//在已排序部分滑动
        while (left!=null&&right!=null){
            if (left.val<right.val){
                if (retNode == null){//只判断一次，retNode是不是没有赋值
                    retNode = left;
                    curNode = left;
                }else {
                    curNode.next = left;//将新的节点添加到已排序链表的后面
                    curNode = left;//更新指针
                }
                left = left.next;
            }else {
                if (retNode == null){//只判断一次，retNode是不是没有赋值
                    retNode = right;
                    curNode = right;
                }else {
                    curNode.next = right;//将新的节点添加到已排序链表的后面
                    curNode = right;//更新指针
                }
                right = right.next;
            }
        }
        if (left!=null)
            curNode.next = left;
        else
            curNode.next = right;
        return retNode;
    }
}

编辑于 2019-06-20 23:39:27 回复(0)

Java

我去个地方啊

题目描述

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3

Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0

Output: -1->0->3->4->5

解题思路

最近忙着追《都挺好》，差点忘记每天的任务。这一题要求时间复杂度为O(n log n) 并且用常数级别的空间复杂度。对于链表这种数据结构，不像数组那么方便，因此堆排序以及快速排序不是很方便，因此这一题用归并排序比较合适，并且对于本题，空间上不需要用数组来存储，因此是常数级别的。

代码提交

class Solution {
    //归并排序的归过程
    public ListNode sortList(ListNode head) {
        //1.判定是否为空或者只有一个元素，这也是归并排序中归的停止条件
        if(head == null || head.next == null){
            return head;
        }

        //2.将链表截成两段
        ListNode pre = null;
        ListNode slow = head;
        ListNode fast = head;

        while(fast != null && fast.next != null){
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }

        //3.此时pre跟slow指的一样，现在将链表从中间断开
        pre.next = null;

        //4.继续再对上面分开的链表再分
        ListNode l1 = sortList(head);
        ListNode l2 = sortList(slow);

        //5.递归分开之后就应该按照一定的规则合并了
        return merge(l1,l2);
    }


    //归并排序的并过程
    private ListNode merge(ListNode l1,ListNode l2){
        //新建一个结点用于串联并过程结果
        ListNode tmp = new ListNode(0);
        ListNode p = tmp;

        //并的过程，谁小谁就接到p后面
        while(l1!=null && l2!=null){
            if(l1.val < l2.val){
                p.next = l1;
                l1 = l1.next;
            }else{
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }

        //如果有一段没有结束，直接接到后面即可
        if(l1 != null){
            p.next = l1;
        }

        if(l2 != null){
            p.next = l2;
        }

        //返回下一个结点
        return tmp.next;
    }
}

发表于 2019-03-22 16:24:19 回复(1)

Java

牛奶椰子糖

/**************
* 归并排序的实现 最终要的在于实现二路归并的算法
* 分成两个部分 对左半部分进行归并排序 对右半部分进行归并排序
* 左右部分进行二路归并
**************/
    public ListNode sortList(ListNode head) {
        //链表长度判断
        if(head==null||head.next==null)
        {
            return head;
        }
        ListNode midNode=findMidNode(head);
        ListNode rightFirst=midNode.next;
        midNode.next=null;
        ListNode leftHead=sortList(head);
        ListNode rightHead=sortList(rightFirst);
        
        return mergeList(leftHead,rightHead);
    }
    /******************
    * 查找链表的中间位置 并返回
    * 查找思路为使用两个引用 一个一次后移两格（快指针），一个一次后移一格(慢指针)
    * 当快指针走到结尾时，慢指针正好走到中间位置
    * 
    *链表节点个数为偶数2n时，fast走到空时 ，slow在n位置
    *链表节点为奇数2n+1时，fast.next为空时，slow在n的位置
    *将链表分为两半时，中间节点分到前半部分
    **************/
    private ListNode findMidNode(ListNode head)
    {
        //为空或只有一个节点
        if(head==null||head.next==null)
        {
            return head;
        }
       //定义快节点和慢节点
        ListNode fastNode=head.next;
        ListNode slowNode=head;
        //直到快节点走到null或者快节点的下一个节点为null
        while(fastNode!=null&&fastNode.next!=null)
        {
            fastNode=fastNode.next.next;
            slowNode=slowNode.next;
        }
        //返回中间位置节点
        return slowNode;
    }
    /********************
    * 链表的二路归并
    * 返回连接后的头节点 类似多项式的合并
    ********************/
    private ListNode mergeList(ListNode first,ListNode second)
    {
        //左边为空 直接返回
        if(first==null)
        {
            return second;
        }
        if(second==null)
        {
            return first;
        }
        ListNode curFirst=first;
        ListNode curSecond=second;
        //找寻头节点 使用first存储 second节点用于
        if(first.val<second.val)
        {
            curFirst=curFirst.next;//指针后移
        }
        else
        {
            first=second;
            curSecond=curSecond.next;
        }
        second=first;//已成链的最后一个节点
        //循环查找 将节点搭在链上
        while(curFirst!=null&&curSecond!=null)
        {
            if(curFirst.val<curSecond.val)
            {
                second.next=curFirst;//将first连接在节点之后
                curFirst=curFirst.next;//first指针后移 指向下一个
            }
            else
            {
                second.next=curSecond;
                curSecond=curSecond.next;
            }
            second=second.next;//链尾新加入一个节点
        }
        //判断哪条链遍历完成
        if(curFirst==null) second.next=curSecond;
        else
        {
            second.next=curFirst;
        }
        //返回头结点
        return first;
    }

发表于 2019-03-10 19:47:14 回复(0)

Java

燃烧的橙子

//思路快速排序

public class Solution {

public ListNode sortList(ListNode head) {
if(head==null||head.next==null)
return head;
ListNode l=null;
ListNode r=null;
ListNode partition=head;
head=head.next;
while(head!=null){
ListNode n=head;
head=head.next;
if(n.val<=partition.val){
n.next=l;
l=n;
}else{
n.next=r;
r=n;
}
}
l=sortList(l);
r=sortList(r);
partition.next=r;

if(l!=null){
ListNode tl=l;
while(tl.next!=null)
tl=tl.next;
tl.next=partition;
return l;
}
else return partition;
}
}

发表于 2018-12-16 23:12:50 回复(0)

Java

Sakula

// 使用快排对单链表排序

public class Solution {

public ListNode sortList(ListNode head) {
quicksort(head, null);
return head;
}

public void quicksort(ListNode start, ListNode end) {
// 如果只有一个节点，递归结束
if (start == end) return ;

ListNode index = partion(start, end);
quicksort(start, index);
quicksort(index.next, end);
}

public ListNode partion(ListNode start, ListNode end) {
// 划分值为头节点
ListNode index = start;
int val = index.val;
ListNode cur = start.next;
while (cur != end) {
// 如果数值比划分值小，则将其与小于等于区间下一位（即index.next）交换，并将小于等于区间(index)下移一位
if (cur.val < val) {
index = index.next;
int tmp = cur.val;
cur.val = index.val;
index.val = tmp;
}
cur = cur.next;
}

// 最后将小于等于区间最后一位和头节点互换
start.val = index.val;
index.val = val;

return index;
}

}

发表于 2018-07-09 16:46:23 回复(0)

Java

中本聪007

import java.util.*;
public class Solution {
public static ListNode sortList(ListNode head) {
ListNode L=head;
ListNode SL=head;//SL用于保存Head节点
if(head==null||head.next==null)
return head;
else{
int i=0;
ArrayList al=new ArrayList();
// ListNode temp=head.next;//此题思路是通过循环取出每个节点的值，然后保存在数组种。

            while(head!=null){//然后用MergeSort进行排序，排完后在对每个节点进行值覆盖，输出SL节点

      al.add(head.val);
head=head.next;
}
int[] a= new int[al.size()];
int[] temp = new int[a.length];
for(i=0;i<al.size();i++) {
    a[i]=(int) al.get(i);
}
MergeSort(a,temp,0,a.length-1);
for(i=0;i<a.length;i++) {
      L.val=a[i];
      L=L.next;
}
}

return SL;
}
    public static void MergeSort(int[] A,int[] temp,int start,int end){
if (start<end){
int mid = (start+end)/2;
//把数组分解为两个子列
MergeSort(A,temp,start,mid);
MergeSort(A,temp,mid+1,end);
//逐级合并两个子列
Merge(A,temp,start,mid,end);
}
}

public static void Merge(int[] A,int[] temp,int start,int mid,int end){
int i = start;
int j = mid+1;
int k = 0;
while(i<=mid&&j<=end){
if (A[i]<=A[j]) {
temp[k] = A[i];
i++;
k++;
}else {
temp[k] = A[j];
j++;
k++;
}
}
while(i<=mid){
temp[k] = A[i];
k++;
i++;
}
while(j <= end){
temp[k] = A[j];
k++;
j++;
}
for (int m = 0; m<k; m++) {
A[start+m] = temp[m];
}
}
}

发表于 2018-06-09 11:06:35 回复(0)

Java

吭哧吭哧埋头干

public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode mid = gitMid(head);
        ListNode midNext = mid.next;
        mid.next = null;
        return mergeSort(sortList(head), sortList(midNext));
    }

    private ListNode mergeSort(ListNode sortList, ListNode sortList2) {
        ListNode preHead = new ListNode(0);
        ListNode curl1 = sortList;
        ListNode curl2 = sortList2;
        ListNode cur = preHead;
        while (curl1 != null && curl2 != null) {
            if (curl1.val < curl2.val) {
                cur.next = curl1;
                curl1 = curl1.next;
            } else {
                cur.next = curl2;
                curl2 = curl2.next;
            }
            cur = cur.next;
        }
        cur.next = curl1 == null ? curl2 : curl1;
        return preHead.next;
    }

    /*
     * 快慢指针
     */
    private ListNode gitMid(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode slow = head;
        ListNode quick = head;
        while (quick.next != null && quick.next.next != null) {
            slow = slow.next;
            quick = quick.next.next;
        }
        return slow;
    }

发表于 2018-05-15 20:45:47 回复(0)

Java

集万千运气于一身

大家不是用的归并就是用的快速，我这贴个偷巧的解法。


import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

/**
 * Created by 怪兽 on 2018/4/17.
 */
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null)
            return null;
        ArrayList<ListNode> list = new ArrayList<>();
        ListNode tmp = head;
        while (tmp != null && tmp.next != null) {
            list.add(tmp);
            tmp = tmp.next;
        }
        list.add(tmp);

        Collections.sort(list, Comparator.comparingInt(o -> o.val));

        ListNode node = list.get(0);
        for(int i = 1;i < list.size();i++){
            node.next = list.get(i);
            node = list.get(i);
        }
        node.next = null;

        return list.get(0);
    }
}

发表于 2018-04-17 11:21:42 回复(0)

Java

傻傻傻傻

public class Solution {
    public ListNode sortList(ListNode head) {
        //利用归并排序，由于链表的特殊性，不会像数组那样需要额外的线性空间
        //1. 首先对于null输入和只有单个节点，直接返回
        if (head == null || head.next == null)
            return head;
        //2. 利用快慢指针，找到链表的中点
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //slow为中点,排序后归并返回
        ListNode midNext = slow.next;
        slow.next = null;
        slow = sortList(midNext);
        head = sortList(head);
        return merge(head, slow);
    }
    private ListNode merge(ListNode head1, ListNode head2) {
        ListNode newHead = new ListNode(Integer.MIN_VALUE);
        ListNode current = newHead;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                current.next = head1;
                head1 = head1.next;
            } else {
                current.next = head2;
                head2 = head2.next;
            }
            current = current.next;
        }
        if (head1 != null) current.next = head1;
        if (head2 != null) current.next = head2;
        return newHead.next;
    }
}

发表于 2017-11-28 10:22:24 回复(0)

Java

探花一笑若奈何

 public class Solution { 

	    public ListNode sortList(ListNode head) {



	        if(head == null || head.next == null)return head;



	        ListNode slow = head;



	        ListNode fast = head.next;



	        while(fast.next != null && fast.next.next != null){



	            slow = slow.next;



	            fast = fast.next.next;



	        }



	        ListNode rightHead = slow.next;



	        slow.next = null;



	        ListNode left = sortList(head);



	        ListNode right = sortList(rightHead);



	        return mergeList(left,right);



	    }



	    private ListNode mergeList(ListNode left,ListNode right){



	        if(left == null)return right;



	        if(right == null)return left;



	        ListNode result;



	        if(left.val < right.val){



	            result = left;



	            left = left.next;



	        }



	        else {



	            result = right;



	            right = right.next;



	        }



	        ListNode slide = result;



	        slide.next = null;



	        while(left != null && right != null){



	            if(left.val < right.val){



	                slide.next = left;



	                left = left.next;



	            }



	            else {



	                slide.next = right;



	                right = right.next;



	            }



	            slide = slide.next;



	        }



	        if(left != null)slide.next = left;



	        if(right != null)slide.next = right;



	        return result;



	    }



	}

编辑于 2017-09-03 13:54:08 回复(0)

链表排序

输入

输出

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

题目描述

解题思路

代码提交

问题信息

热门推荐

通过挑战的用户

相关试题