链表的插入排序

import java.util.*;

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

public class Solution {
    /**
     *  需要使用插入排序，
     1.创建头节点为虚节点，将虚节点指针指向原头节点
     2.循环  从原头节点第二个node开始 往前 判断，是否存在比该节点大得数据，存在则交换指针，
     3.每循环一次，都需要将记录下次需要遍历node得引用，
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode insertionSortList (ListNode head) {
        if(head==null||head.next==null)return head;
        //创建头节点
        ListNode tempNode =new ListNode(0);
        //连接指针
        tempNode.next=head;
        //从第二个节点开始遍历是否需要插入
        ListNode current =head.next;
        //设置引用对象，交换指针得时候需要有  3个节点得指针变动，
        //pre节点得next指向currentNode，
        //currentNode得上一节点得next需要指向currentNode得next
        //currentNode得next指向pre节点得next
        //如果需要指针变动，则会把当前节点插入到前面，所以currentLast指针不用变动，
        //如果不需要指针变动，则下次循环得时候currentLast指针为currentLast得next节点
        ListNode next,pre,currentLast=head;
        while (true){
            pre=tempNode;
            if(current==null)break;
            next=current.next;
            while (pre.next.val<current.val){
                pre=pre.next;
            }
            if(pre.next!=current){
                //交换  1,2,3,4,
                currentLast.next = next;
                current.next =pre.next;
                pre.next = current;
            }else{
                currentLast = current;
            }
            current=next;
        }
        return tempNode.next;
    }
}

import java.util.*;

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

public class Solution {
    /**
     * 找到小的节点，然后从开头遍历插入改节点
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode insertionSortList (ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        //记录从头部节点开始进行插入后面一个较小的值，插入完成后重置执行head
        ListNode p = head;
        //设置哨兵节点，用于记录头部
        ListNode preHead = new ListNode(0);
        preHead.next = head;
        //记录前一个节点
        ListNode pre = head;
        //比较的当前节点，从第二个开始比较
        ListNode cur = head.next;
        while (cur != null){
            //找到小的节点
            if (cur.val < pre.val){
                //切分当前节点
                ListNode temp = cur;
                pre.next = cur.next;
                cur.next = null;
                cur = pre.next;
                //循环从前往后插入该节点
                ListNode pr = preHead;
                while (p != cur){
                    if (temp.val < p.val){
                        pr.next = temp;
                       temp.next = p;
                       break;
                    }
                    p = p.next;
                    pr = pr.next;
                }
                //重置
                p = preHead.next;
            }else {
                cur = cur.next;
                pre = pre.next;
            }
        }
        return preHead.next;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode newHead = new ListNode(0);//新建一个链表表头
        ListNode cur = head.next;//原链表上的指针

        //将原链表的表头即第一个节点从原链表上断开，并接到新链表上
        head.next = null;
        newHead.next = head;
        
        ListNode newCur = newHead.next;//新链表上的指针
        //依次取出原链表中的节点，从原链表上断开之后按顺序插入新链表上对应的位置
        while(cur != null){
            ListNode node = cur;//取出cur所指向的原链表中的当前节点node
            cur = cur.next;//cur指针后移一位
            node.next = null;//将node从原链表上断下来
            if(node.val >= newCur.val){
                //如果node的值比新链表尾节点（即newCur所指节点）的值大或相等，则直接插在新链表末尾即可
                newCur.next = node;
                newCur = newCur.next;//注意别忘了将新链表指针newCur后移一位
            }else{
                //如果node的值比新链表尾节点（即newCur所指节点）的值小，则从新链表首节点的下一节点开始查找第一个next节点的值比node值大的节点
                ListNode p = newHead;
                //依次向后遍历，直到p的值比node值小，但p.next的值比node值大时为止，这时node应该插在p节点后面
                while(p.next.val<node.val){
                    p = p.next;
                }
                //把node插在p节点后面即可
                node.next = p.next;
                p.next = node;
            }
        }
        //注意返回的是newHead的下一个节点才是真正的首节点
        return newHead.next;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head==null||head.next==null)
            return head;
        ListNode tail,nex,i,t;
        tail=head;
        nex=head.next;
        tail.next=null;
        out:
        while(nex!=null){
            t=nex;
            nex=nex.next;
            if(t.val<head.val){
                t.next=head;
                head=t;
            }
            else{
                i=head;
                while(i.next!=null){
                    if(t.val<i.next.val){
                        t.next=i.next;
                        i.next=t;
                        continue out;
                    }
                    i=i.next;
                }
                t.next=i.next;
                i.next=t;
            }
        }
        return head;
    }
}

public class Solution {
    public ListNode insertionSortList(ListNode head) {
                if (head == null || head.next == null)
            return head;
        // pre指向有序表的尾部节点
        ListNode pre = head;
        // cur指向待排序表头部的节点
        ListNode cur = head.next;
        // 辅助节点，用于节点插入
        ListNode aux = new ListNode(-1);
        aux.next = head;
        while (cur != null) {
            if (cur.val < pre.val) {
                // 先把cur节点删除，然后再插到合适位置
                pre.next = cur.next;
                // l1,l2双指针，用于cur节点插入
                ListNode l1 = aux;
                ListNode l2 = aux.next;
                //从表头往后找到l2.val大于cur.val的地方，
                                //把cur插到l1,l2之间
                while (cur.val > l2.val) {
                    l1 = l2;
                    l2 = l2.next;
                }
                 //把cur节点插入到l1和l2之间
                l1.next = cur;
                cur.next = l2;
                //指向下一个待处理节点
                cur = pre.next;
            } else {
                pre = cur;
                cur = cur.next;
            }
        }
        return aux.next;
    }
}

public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head==null)
            return head;
        ListNode node1=head;
        ListNode node2=head.next;
        while(node1.next!=null){
            while(node2!=null){
                if(node1.val>node2.val){
                    int tem=node1.val;
                    node1.val=node2.val;
                    node2.val=tem;
                }
                node2=node2.next;
            }
            node1=node1.next;
            node2=node1.next;
        }
        return head;
    }
}

题目描述

Sort a linked list using insertion sort.

解题思路

解题思路就是根据插入排序的思想，每次遍历都保证前n个数都是排好序的，那么按照原生的插入排序，是从当前元素前一个元素开始一个一个往前判断，只要比前面元素小，则往前移动，一直移动到有一个元素小于它或者移动到头部了则停止，这个位置就是当前元素在这一趟中应该在的位置。但是链表中不好往前移，只能每次都从头部开始往后判断，一直找到第一个比当前元素大的元素停止，然后调整一下指针，就是让当前元素插入到本趟合适的位置。由于有可能要与第一个元素交换，所以搞一个虚拟头节点处理起来会简单一点。

代码提交

class Solution {
    public ListNode insertionSortList(ListNode head) {
        //1.判断一下
        if(head == null || head.next == null){
            return head;
        }
        //2.新建一个虚拟节点，后面要用
        ListNode dummy = new ListNode(0);
        //3.curr指向的节点及其后面所有节点都是未排序的，前面的都是排好序的
        ListNode curr = head;
        while(curr != null){
            //4.每次循环，pre都重新指向dummy，dummy后一个节点到curr前一个节点都是排好序的
            ListNode pre = dummy;
            //5.保存一下当前节点后面一个节点的引用
            ListNode next = curr.next;
            //6.每次都从dummy节点下一个开始找，前面都是排好序的，如果小于当前节点则指针后移，一直找到pre.next为空
            //或者比当前节点大的时候，停止，表明pre的下一个节点就是当前节点应该放的位置
            while(pre.next != null && pre.next.val < curr.val){
                pre = pre.next;
            }
            //7.找到当前节点应该放的位置之后，下面的工作就是移动指针，让curr插到pre和pre.next中间
            //然后让curr后移一位，前面都是排好序的
            curr.next = pre.next;
            pre.next = curr;
            curr = next;
        }
        //8.dummy后面就是我们所需要的用插入排序排好序的链表
        return dummy.next;
    }
}

import java.util.*;
public class Solution {
    public static ListNode insertionSortList(ListNode head) {
        ListNode L=head;
        ListNode SL=head;
        if(head==null||head.next==null)
            return head;
        else{
            int i=0;
            ArrayList al=new ArrayList();
            while(head!=null){
                al.add(head.val);
                head=head.next;
            }
            int[] a= new int[al.size()];
            for(i=0;i<al.size();i++) {
                a[i]=(int) al.get(i);
            }
            getInsertSort(a);//和上一题一样，只不过换了一个排序算法，主方法里面几乎没变。
            for(i=0;i<a.length;i++) {
                L.val=a[i];
                L=L.next;
            }
        }
                 return SL;
    }     public static void getInsertSort(int[] a) {
        int n = a.length;//将数组的长度赋给n是为了防止每次for循环中判断时都调用length方法影响性能
        int temp;//放于for循环外面是为了防止重复创建变量
        int j;
        for(int i = 1; i < n;i++){//排序的趟数
            temp = a[i];//赋给temp是为了防止索引i之前的元素向后移动覆盖了索引i的元素
            j = i-1;
            for(; j>=0&&a[j]>temp; --j) {//将大于i位置元素的元素向后移
                a[j+1] = a[j];
            }
            a[j+1]= temp;//找到i应该在的位置，将值放置此处 
        }
    }
}

public ListNode insertionSortList(ListNode head) { if (head == null || head.next == null) { return head;
    } // 9->8->12->6->18，sortNode为要比较的  ListNode sortNode = head.next;
    ListNode tempNode = new ListNode(-1); // 要替换的前一个tempNode  ListNode preNode;
    tempNode.next = head; // 将head的后面设置为null  head.next = null; while (sortNode != null) {
        ListNode tempNodeCopy = tempNode.next;
        ListNode next = sortNode.next;
        preNode = tempNode; while (tempNodeCopy != null && tempNodeCopy.val <= sortNode.val) {
            preNode = preNode.next;
            tempNodeCopy = tempNodeCopy.next;
        }
        preNode.next = sortNode;
        sortNode.next = tempNodeCopy;
        sortNode = next;
    } return tempNode.next;
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode myHead = new ListNode(Integer.MIN_VALUE);
        ListNode tmpNode = head;
        while (tmpNode != null) {
            ListNode indexNode = myHead;
            for (; indexNode.next != null && indexNode.next.val < tmpNode.val; indexNode = indexNode.next) {
            }
            ListNode nextNode = tmpNode.next;
            tmpNode.next = indexNode.next;
            indexNode.next = tmpNode;
            tmpNode = nextNode;
        }
        return myHead.next;
    }
}

	    public ListNode insertionSortList(ListNode head) {
               if(head==null || head.next==null)
                   return head;
               
             ListNode q=head.next ;                    
             while(q!=null) {
                 ListNode t=head;  
               while(t!=q) {
                   if(t.val>q.val) {
                       int tmp=t.val;
                       t.val=q.val;
                       q.val=tmp;
                   }
                  t=t.next; 
               }
                 q=q.next;
          }
        return head;
    }

	/*



	* 由于不能直接判断两个结点是否相等，因此用两个整数指标来判断每次的迭代是否到达当前有序



	* 队列的队尾；用结点分别记录有序部分的迭代结点前面的结点和队尾结点，方便插入操作 



	*/



	public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        //为了避免处理当前结点最小，需要更换头结点的特殊情况，



	      //添加哑结点，值为最小整数，作为头结点
        ListNode dumy = new ListNode(Integer.MIN_VALUE);
        dumy.next = head;
        ListNode first;//first表示前面有序部分的迭代结点
        ListNode second;//second表示将要向前面有序部分链表插入的结点



	      //分别记录first前面的一个节点和有序部分的尾结点        



	      ListNode beforeFirst, tmpTail;
        beforeFirst = dumy;
        tmpTail = dumy;
        int i, j;//用于判断first结点是否到达有序部分队尾
        for (second = dumy.next, i = 1; second != null;  ++ i)
        {
            for (first = dumy, j = 0; j < i; beforeFirst = first, first = first.next, ++ j)
            {
                //如果second结点值比某一个first结点值小，



	            //则将second结点值插入beforeFirst和first结点中间，并跳出内循环
                if (first.val > second.val)
                {
                    tmpTail.next = second.next;



	               //将second结点插入beforeFirst与first之间  



	                    second.next = first;



	               beforeFirst.next = second;
                    break;
                }
            }



	//说明second结点值比当前有序链表中值都大，则直接添加second在有序链
            if (i == j)表最后，并更新尾结点
                tmpTail = second;
            second = tmpTail.next;//更新要插入的结点
        }
        return dumy.next;
    }
}

/*
手动模拟插入排序的过程啊，用h节点来遍历，temp1节点寻找插入的位置，找到后用temp2记录要插入的位置，
之后将整个链表后移到当前元素所在位置，后移的时候使用val来记录下一个节点原来的值。
*/

public ListNode insertionSortList(ListNode head) {
    ListNode h = head;
    while(h!=null){
        ListNode temp1 = head;
        while(temp1 != h && temp1.val <= h.val){
            temp1 = temp1.next;
        }
        if(temp1!=null && temp1 != h){
            ListNode temp2 = temp1;
            int val = temp1.val;
            while(temp1 != h){
                temp1.next.val ^= val;val ^= temp1.next.val;temp1.next.val ^= val;
                temp1 = temp1.next;
            }
            temp2.val = val;
        }
        h = h.next;
    }
    return head;
}

//使用插入排序，将一个链表进行排序
//思路：插入排序的思路是将一个数字插入到一个已经排序好的序列中，本题目中是链表
//所以我们可以新建一个链表，之后新链表中存放排序好的节点。循环遍历原链表，依次
// 在新链表中进行比较，之后进行插入操作
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head == null || head.next==null){
            return head;
        }
        //创建一个新节点(头结点)，保存排序好的节点
        ListNode sortNode = new ListNode(0);
        ListNode pCur = head;
        //ListNode sortHead = sortNode;
        while(pCur != null){
            //保存当前节点的下一个节点
            ListNode nodeNext = pCur.next;
            //得到排序好的链表的头指针
            ListNode sortHead = sortNode;
            //寻找插入位置
            while(sortHead.next != null && sortHead.next.val < pCur.val){
                sortHead = sortHead.next;
            }
            //找到位置将pCur进行插入到有序链表中
            pCur.next = sortHead.next;
            sortHead.next = pCur;
            //更新pCur节点
            pCur = nodeNext;
        }
        return sortNode.next;
    }
}