对链表进行插入排序

[编程题]对链表进行插入排序

热度指数：1646 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

对链表进行插入排序，

从链表第一个元素开始可以视为部分已排序，每次操作从链表中移除一个元素，然后原地将移除的元素插入到已排好序的部分。

数据范围：链表长度满足 $1 \le n \le 1000\$ ，链表中每个元素满足 $|val| \le 10000 \$

例如输入{2,4,1}时，对应的返回值为{1,2,4}，转换过程如下图所示：

示例1

输入

{1,2,3}

输出

{1,2,3}

示例2

输入

{2,4,1}

输出

{1,2,4}

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

算法知识视频讲解

Java

晚梦忆笙歌

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode insertionSortList (ListNode head) {
        // write code here
        ListNode dummyHead = new ListNode(-10001);
        while (head != null) {
            ListNode temp = head.next;
            head.next = null;
            insertNode(dummyHead, head);
            head = temp;
        }
        return dummyHead.next;
    }

    public void insertNode(ListNode dummyHead, ListNode node) {
        ListNode prev = dummyHead;
        ListNode cur = dummyHead.next;
        while (cur != null) {
            if (node.val < cur.val) {
                prev.next = node;
                node.next = cur;
                return;
            }
            prev = cur;
            cur = cur.next;
        }
        prev.next = node;
    }
}

发表于 2023-12-18 00:29:01 回复(0)

Java

爱睡觉的杨大爷

import java.util.*;
public class Solution {
    //从头插入和从中间插入和从尾部插入都是不一样的
    public ListNode insertionSortList (ListNode head) {
        // 设置一个pre指针
        ListNode pre=head;
        head=head.next;
        pre.next=null;
        //左边已排序的链表形成
        boolean flag=true; //用于标记右边链表的当前节点是否已经插入
        while(head!=null){
            flag=true;
            ListNode next=head.next;
            head.next=null;  //从链表中移除
             if(head.val<=pre.val){  //从左边链表头插入
                    head.next=pre;
                    pre=head;
                    flag=false;  //如果从头节点就已经插入，把标志赋值为flase
                }
            ListNode pcur=pre;
            ListNode cur=pre.next;   //从排序的链表头节点开始
            while(flag&&cur!=null ){ //如果在中间插入，需要两个节点
               if(head.val<=cur.val){
                   pcur.next=head;
                   pcur=head;
                   pcur.next=cur;
                   flag=false;
                   break;
               }
                cur=cur.next;
                pcur=pcur.next;
            }
            //如果走到尾部依然还没有插入，就把这个节点插入尾部
            if(flag){
                pcur.next=head;
            }
            //节点插入完毕，进行下一个节点
            head=next;
        }
        return pre;   
    }
}

发表于 2022-07-30 21:34:28 回复(0)

Java

pein531

和数组的插入排序流程基本相同，但考虑到单链表只能向后寻找元素，因此维持的有序区域为降序，待整个链表有序后再将链表进行反转。

先将头节点作为有序区域的边界sortedHead，然后循环遍历后面待排序的节点waitingForSort；
在某次循环中，拿当前的待排序节点waitingForSort与有序区域的边界节点sortedHead（即头结点）进行比较。如果比边界节点的值小，就往后面寻找自己可以插入的点，否则就成为有序链表新的头节点；
当前的待排序节点完成插入后，就考虑下一个待排序节点应该插入到有序区域的位置，周而复始直到没有待排序节点；
最后将有序区域的链表sortedHead进行反转。

import java.util.*;

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode insertionSortList (ListNode head) {
        // write code here
        if(head == null || head.next == null) return head;
        ListNode sortedHead = head;            // 有序部分边界(降序)
        ListNode waitingForSort = head.next;   // 待排序部分头结点
        head.next = null;                      // 有序和待排序部分断开
        while(waitingForSort != null){
            if(waitingForSort.val >= sortedHead.val){
                ListNode newHead = waitingForSort;
                waitingForSort = waitingForSort.next;      // 待排序的下一个节点
                newHead.next = sortedHead;
                sortedHead = newHead;
            }else{
                ListNode prev = null;
                ListNode cur = sortedHead;
                // 待排序部分小于有序部分的结点就不断往后换
                while(cur != null && waitingForSort.val < cur.val){
                    prev = cur;
                    cur = cur.next;
                }
                if(cur != null){
                    // 中间找到了某个位置可以插入，待排序节点插入在prev和cur之间
                    ListNode newNode = waitingForSort;
                    waitingForSort = waitingForSort.next;
                    newNode.next = cur;
                    prev.next = newNode;
                }else{
                    ListNode newTail = waitingForSort;
                    prev.next = newTail;
                    waitingForSort = waitingForSort.next;
                    newTail.next = null;
                }
            }
        }
        return reverseList(sortedHead);
    }
    
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}

发表于 2021-12-13 13:21:20 回复(0)

Java

嘎嘎皮

java递归解法

import java.util.*;
public class Solution {
    public ListNode insertionSortList (ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode node = insertionSortList(head.next);
        ListNode p = node, pre =null;
        while(p != null){
            if(p.val < head.val){
                pre = p;
                p = p.next;
            }
            else{
                break;
            }
        }
        if(pre == null){
            head.next = p;
            return head;
        }
        head.next = p;
        pre.next = head;
        return node;
    }
}

发表于 2021-12-07 15:41:13 回复(0)