BM12 单链表的排序

目录

题目链接

题目

解题思路

代码

题目链接

单链表的排序_牛客题霸_牛客网

题目

解题思路

法一：值排序：遍历一遍链表将所有值放在一个集合中,然后排序,然后重新放入即可

法二：归并排序：先使用快慢指针将链表分为左右,然后一直递归到最小,最后归并,将小的连接在前面,最后返回即可

代码

法一：值排序

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
        ListNode dummyNode=new ListNode(-1);
        ListNode cur=head;
        ArrayList<Integer> array=new ArrayList<>();
        while(cur!=null){ 
            array.add(cur.val);
            cur=cur.next;
        }
        Collections.sort(array);
        dummyNode.next=head;
        cur=head;
        for(int i=0;i<array.size();i++){
            cur.val=array.get(i);
            cur=cur.next;
        }
        return dummyNode.next;
    }
}

法二：归并排序

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 slow,fast;
        slow=head;
        fast=head.next;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode newhead=slow.next;
        slow.next=null;
        ListNode left=sortInList(head);
        ListNode right=sortInList(newhead);
        ListNode dummyNode=new ListNode(-1);
        ListNode cur=dummyNode;
        while(left!=null&&right!=null){
            if(left.val<right.val){
                cur.next=left;
                left=left.next;
            }else{
                cur.next=right;
                right=right.next;
            }
            cur=cur.next;
        }
        cur.next=left==null?right:left;
        return dummyNode.next;
    }
}