首页 > 试题广场 >

链表的插入排序

[编程题]链表的插入排序
  • 热度指数:62814 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
使用插入排序对链表进行排序。
示例1

输入

{30,20,40}

输出

{20,30,40}

说明:本题目包含复杂数据结构ListNode,点此查看相关信息
ListNode *insertionSortList(ListNode *head) {
        if (!head)
            return head;
        
        ListNode tmp(0);
        ListNode* p, *q, *t;
        while (head) {
            p = &tmp;
            q = p->next;
            t = head;
            head = head->next;
            while (q && q->val < t->val) {
                p = p->next;
                q = q->next;
            }
            t->next = q;
            p->next = t;
        }
        
        return tmp.next;
    }
//对这里面很多人表示无语,人家说插入排序,
//我看排行榜里面很多人直接push节点到一个list,
//sort一下,然后重新组织下链表。这些答案有何意义?
//请管理员对这些答案进行清除。

编辑于 2016-10-11 17:44:07 回复(16)
//这题不是让用插入排序吗。。。评论里怎么各式各样的。。
//解释下:
// 插入排序就是不断的向一个已经排序的列表中(此处为代码中的sortedList)添加新的节点,并且保证添加节点后的列表仍然有序。
//     一开始的时候sortedList为空,需要遍历输入链表(也就是未排序链表,此处为形参head)的每一个节点,每遍历一个,sortedList加一个。 
//      cur代表的就是你当前要加入sortedlist的节点。cur要插入的位置在sortedList的哪里呢?就是此处代码中node的后面。 经过这么一轮,一个节点就被加入到了sortlist。之后同理。 /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        if(head==nullptr || head->next==nullptr) return head;
        
        //在插入时,有可能需要在链表头插入,为了方便,新建立个链表
        ListNode sortedList(0);
        ListNode *cur=head;
        
        while(cur){
            //因为cur的指向可能会改变,所以要预先存下cur的next,以备在下次循环时使用
            ListNode *next=cur->next;
            
            //node代表排序数组的当前节点
            //从前向后遍历排序数组的每一个节点,和当前未排序数组中的节点做比较            
            ListNode* node=&sortedList;
            while(node->next!=nullptr && node->next->val<cur->val) //以为第一个元素是0,所以从next开始
            {
                node=node->next;
            }
            
            cur->next=node->next;
            node->next=cur;
            cur=next;
        }
        
    	return sortedList.next;

    }
};

编辑于 2017-05-03 23:09:06 回复(5)
// 1. 添加了个伪链表头,简化设计
// 2. 利用递归
class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        if(!head || !head->next) return head;
        ListNode dummyHead(0), *p;
        dummyHead.next = insertionSortList(head->next);
        p = &dummyHead;
        
        while(p && p->next && head->val > p->next->val){
            p = p->next;
        }
        head->next = p->next;
        p->next = head;
        
        return dummyHead.next;
    }
};

发表于 2016-08-02 17:44:54 回复(14)
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head==null||head.next==null)
			return head;
		ListNode cursors = head;
		ListNode tempCur = null;
		ListNode temp = head;//待排序元素的上一元素
		ListNode current = temp.next;//待排序的元素
		while(current!=null){
			if(current.val<head.val){
				//排序的元素比头小 把当前元素当做头
				temp.next = current.next;
				current.next = head;
				head = current;
			}else{
				//     cursors-↓    ↓-temp
				//   1 -> 3 -> 5 -> 8 -> 4-> 12 -> 2
				//tempCur-↑      current-↑
				//插入后:
				//  |-------有序---------|
				//  1 -> 3 -> 4 -> 5 -> 8-> 12 -> 2
				//找到插入的位置 current插入到cursors的前面:temp->current->cursors
				tempCur = cursors;
				cursors = tempCur.next;
				while(cursors!=current&&cursors.val<current.val){
					tempCur = cursors;
					cursors = cursors.next;
				}
				if(cursors==current){
					temp = current;
					current = temp.next;
				}else{
					temp.next = current.next;
					tempCur.next = current;
					current.next = cursors;
				}
				
			}
			cursors = head;
			current = temp.next;
		}
        return head;
    }
}

发表于 2016-05-30 15:35:13 回复(6)
/*思路:1.判断head和head->next是否为NULL
        2.将head作为有序链表,将head->next作为待插入的链表,所以讲head和head->next分开(head->next=NULL)
        3.比较大小的三种情况:(1)与头结点比较
                              (2)考虑pA=pA->next的情况
                              (3)其他
*/


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        if (head == NULL || head->next == NULL) {
            return head;
        }
        ListNode* pB = head->next;
		head->next = NULL;
		ListNode *pA, *temp;
		while (pB != NULL) {
			pA = head;
			if (pB->val < head->val) {
				temp = pB->next;
				//pB->next = head;
				pB->next = pA;
				head = pB;
				pB = temp;
			}
			else {
				while (pA->next != NULL && pA->next->val < pB->val) {
					pA = pA->next;
			}
			temp = pB->next;
			pB->next = pA->next;
			pA->next = pB;
			pB = temp;
            }
        }
        return head;
    }
};

发表于 2016-06-23 14:34:57 回复(0)

题目描述

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;
    }
}
编辑于 2019-03-23 20:06:51 回复(5)
class Solution {
public:
  ListNode* insertionSortList(ListNode* head) {
    
    ListNode dummy(INT_MIN);
    ListNode *tail = &dummy, *curr = head;
    
    while (curr) {
      if (tail->val <= curr->val) {
        tail = tail->next = curr;
        curr = curr->next;
      } else {
        tail->next = curr->next;
        ListNode* p = &dummy;
        
        while (p->next->val < curr->val) p = p->next;
        curr->next = p->next;
        p->next = curr;
        
        curr = tail->next;
      }
    }
    
    return dummy.next;
  }
};

发表于 2021-09-23 09:14:09 回复(0)
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应该在的位置,将值放置此处 
        }
    }
}

发表于 2018-06-09 11:16:47 回复(0)
public class Solution {
    public ListNode insertionSortList(ListNode head) {
		if(head == null || head.next == null) return head;
		ListNode r = head.next;
		head.next = null;
		while (r != null) {
			ListNode q = head;
			ListNode p = null;
			while (q != null && q.val < r.val) {
				p = q;
				q = q.next;
			}
			ListNode t = r.next;
			if(q == head) {
				r.next = head;
				head = r;
			} else {
				p.next = r;
				r.next = q;
			}
			r = t;
		}
		return head;
	}
}
编辑于 2017-03-19 15:26:11 回复(1)
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        if(head==NULL)
            return head;
		ListNode* p=head->next;
		ListNode* q=head;
		ListNode* r=head;
		//s=head;
		while(p!=NULL){
		    if(p->val>=q->val){
				p=p->next;
				q=q->next;
			}
			else if(p->val<head->val){
				q->next=p->next;
				p->next=head;
				head=p;
				//p,q update
				p=q->next;
			}

			else{
				r=head;
				while(r->next->val<p->val){
				    r=r->next;
				}
				q->next=p->next;
				p->next=r->next;
				r->next=p;
				p=q->next;
				
			}
			
		}
        return head;
			
		
    }
};

发表于 2016-09-04 16:54:41 回复(0)
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        ListNode *dummyHead = new ListNode(-1);
        ListNode *p1 = dummyHead, *p2 = head, *prev;
        while (p2 != nullptr) {
            while (p1 -> next != nullptr) {
                prev = p1;
                p1 = p1 -> next;
                if (p1 -> val > p2 -> val) {
                    ListNode* rest = p2 -> next;
                    prev -> next = p2;
                    p2 -> next = p1;
                    p2 = rest;
                    p1 = dummyHead;
                    break;
                }
            }
            if (p1 -> next == nullptr) {
                ListNode* rest = p2 -> next;
                p1 -> next = p2;
                p2 -> next = nullptr;
                p2 = rest;
                p1 = dummyHead;
            }
        }
        
        return dummyHead -> next;
    }
};

发表于 2020-03-10 22:07:10 回复(0)
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode emptyNode = new ListNode(Integer.MIN_VALUE);
        while(head != null){
            ListNode outNextNode = head.next, innerNode = emptyNode;
            while(innerNode.next != null && head.val > innerNode.next.val){
                innerNode = innerNode.next;
            }
            head.next = innerNode.next;
            innerNode.next = head;
            head = outNextNode;
        }
        return emptyNode.next;
    }
}

编辑于 2019-10-05 11:52:44 回复(1)
// 我觉得题目的本意是要求使用在原数组上进行插入排序,而不是新建链表、保存变量到容器排序后在写到原链表; //我的思路是:选中当前的结点 对比前面的所有结点(插入排序默认前面的结点都是排好序的)         //如果都大于前面的结点则保持原地不动         //如果从头排序好的结点,如果出现小于本身的结点,则从链表上摘下自身节点并插入到比自己小的结点前面 //另外方便头结点的数据操作,增加了头指针辅助变量 class Solution { public:     ListNode *insertionSortList(ListNode *head) {      if (head == NULL) return NULL;      //建立辅助头指针      ListNode * root = (ListNode *)malloc(sizeof(ListNode));      root->next = head;
     ListNode * current = head->next;  //被比较的结点      ListNode * pre_current = head;    //当前结点的前一个结点      while (current != NULL)      {           ListNode * temp = root->next;     //类似迭代器           ListNode * pre_temp = root;       //指向前一个指针           while (temp->val <= current->val && temp != current)           {            temp = temp->next;            pre_temp = pre_temp->next;           }               if (temp != current)           {                //删除当前节点                deleteSortList(pre_current, current);                //添加到合适的结点                insertSortList(pre_temp, current);                current = pre_current->next;           }           else {                //更改循环变量                current = current->next;                pre_current = pre_current->next;           }      }      head = root->next;      free(root);      return head;     } private:     ListNode *deleteSortList(ListNode *pre_ptr,ListNode *cur_ptr)     {         ListNode * del_ptr = cur_ptr;         pre_ptr->next = del_ptr->next;         return del_ptr;     }     void insertSortList(ListNode *pre_ptr,ListNode *add_ptr)     {         add_ptr->next = pre_ptr->next;         pre_ptr->next = add_ptr;     } };

发表于 2019-05-29 02:46:08 回复(0)
Solution 1
/*
下面是效仿数组的插入排序的一种方法。
*/
class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        if(head==nullptr||head->next==nullptr) 
            return head;
        ListNode *p,*q;
        p=head->next;
        while(p!=nullptr)//从第二个元素开始插入
        {
            q=p->next;
            p->next=nullptr;//将插入元素后指针置nullptr
            InsertList(head,p,q);
            p=q;
        }
        return head;
    }
private:
    void InsertList(ListNode *&front,ListNode *obj,ListNode *_next)
    {
        ListNode *NewNode=new ListNode(obj->val);
        ListNode *q,*p;
        p=front;
        q=front->next;
        while(!(q->val==obj->val&&q->next==nullptr))//将待插指针从链表尾中删除
        {
            p=p->next;
            q=q->next;
        }
        p->next=nullptr;
        q=front;
        if(q->val>obj->val)//当链表第一个元素大于待插元素时
        {
            NewNode->next=front;
            front=NewNode;
            while(q->next!=nullptr)
                q=q->next;
            q->next=_next;//将差值完成的链表与后链表接起来
        }
        else{
            ListNode *temp;
            while(q!=nullptr)
           {
             if(q->val<obj->val)//寻找插入位置
             {
                 temp=q;
                 q=q->next;
             }
                else break;
           }
            if(q!=nullptr)//插入位置在链表中间某个位置
            {
                temp->next=NewNode;
                NewNode->next=q;
                 while(q->next!=nullptr)
                    q=q->next;
                 q->next=_next;
            }
            else{  //插入位置在链表尾部
                temp->next=NewNode;
                NewNode->next=_next;
            }
        }
        return ;
    }
};

Solution 2
class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        if(head==nullptr||head->next==nullptr)
            return head;
        ListNode *NewList=new ListNode(0);
        ListNode *q,*p,*pre;
        while(head!=nullptr)
        {
            pre=NewList;
            q=pre->next;
            p=head;
            head=head->next;
            while(q!=nullptr&&q->val<p->val)
            {
                pre=pre->next;
                q=q->next;
            }
            pre->next=p;
            p->next=q;
        }
        return NewList->next;
    }
};


编辑于 2019-04-25 22:00:59 回复(0)
/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/

/*
看了大家提交的c++代码,几乎都是用链表或者其他辅助数据结构存下所有元素,然后用现成的sort函数排序
这种方式不是本题的考察意图,虽然复杂度等因素导致这种答案也能通过测试用例,不过本题的要求是“插入排序”。
“插入排序”,简单点说,就是从混乱待排的数据中,每次选一个插入到已有序的数据中合适的位置。
所以,把xcyok同学的java代码翻译成c++的如下:
*/
class Solution {
public:
ListNode *insertionSortList(ListNode *head) {
if(head == nullptr) return head;
ListNode* dummy = new ListNode(0x80000000);//这个新链表头节点用来存已经有序的链表,val初始化为最小值
ListNode* cur = head;//从头开始处理“待排序链表”
ListNode* pre = dummy;//“已经有序链表”中的查找指针,方便找目的合适的位置
while(cur != nullptr)
{
ListNode* next = cur->next; //存下原链表中当前位置cur的下一个指针,预防断了没法继续判断
pre = dummy; //从已经有序的元素开始找.由于在已有序的链表中还是尾插,所以每次从头开始遍历
while(pre->next != nullptr && pre->next->val < cur->val)//一直找到合适的待插位置
{
pre = pre->next;
}
cur->next = pre->next;//插入合适的位置操作1
pre->next = cur;//插入合适的位置操作2
cur = next;//更新原链表中待判断的后续元素位置
}
return dummy->next;//返回链表,不包含新增的临时节点
}
};

编辑于 2019-05-14 22:25:14 回复(0)
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0);

        while(head != null){
            ListNode node = dummy;

            while(node.next != null && node.next.val < head.val){
                node = node.next;
            }

            ListNode tmp = head.next; //保存head的下一个节点
            head.next = node.next;  //拼接排序后半部分数组
            node.next = head;   //把前半部分排序数组和后半部分凭借
            head = tmp;  // 恢复head的下一个节点
        }

        return dummy.next;
    }
}
发表于 2018-09-06 15:08:55 回复(0)
#这个题目我是完全按照插入排序来写的,思路如下:
#1.在第i次循环中,找到当前链表第i个节点到最后一个节点中中key最小的节点,将其插入第i-1个位置
#需要注意如果temp == head,head需要前进一步,否则死循环。
class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        if (head == NULL || head->next == NULL)
            return head;
        ListNode* min = new ListNode(INT16_MAX);
        ListNode* runner;
        ListNode* res = new ListNode(0); res->next = head;
        ListNode* copy = res;
        while (head->next != NULL) {
            runner = head;
            min = new ListNode(INT16_MAX);
            min->next = head;
            while (runner != NULL) {
                if (runner->val < min->next->val) {
                    while (min->next != runner)
                        min = min->next;
                    //break;
                }
                runner = runner->next;
            }
            ListNode*temp = min->next;
            if (temp == head)
                head = head->next;
            min->next = min->next->next;
            res->next = temp;
            temp->next = head;
            //head = head->next;
            res = temp;
        }
        return copy->next;
    }
};
发表于 2018-08-29 01:07:33 回复(0)
//感觉自己写的太麻烦 我怎么感觉加了一个伪表头,反而麻烦了
public ListNode insertionSortList(ListNode head){
        if(head==null||head.next==null)
            return head;
        ListNode first =new ListNode(-1);
        ListNode curIndex,last,slow,fast;
        first.next=head;
        last=head;
        curIndex=head.next;
        last.next=null;
        while(curIndex!=null){
            //大于头节点
            if(curIndex.val<=head.val){
                first.next=curIndex;
                curIndex=curIndex.next;
                first.next.next=head;
                //last=head;
                head=first.next;
            }
            else if(curIndex.val>last.val){
                last.next=curIndex;
                last=last.next;
                curIndex=curIndex.next;
                last.next=null;
            }
            else{
                slow=head;
                fast=head.next;
                while(fast.val<curIndex.val){
                    slow=fast;
                    fast=fast.next;
                }
                slow.next=curIndex;
                curIndex=curIndex.next;
                slow=slow.next;
                slow.next=fast;
            }
        }
        return first.next;
    }
发表于 2017-11-17 20:35:09 回复(0)
class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        if(head==NULL || head->next==NULL)
        	return head;
        ListNode L(0),*p;
		L.next = insertionSortList(head->next);
		p = &L;
		
		while(p && p->next && p->next->val < head->val)
			p = p->next;
		head->next = p->next;
		p->next = head;
		
		return L.next;
    }
};

发表于 2017-09-07 00:59:00 回复(0)
class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
       if(head == nullptr || head->next == nullptr){
           return head;
       } 
       ListNode *pstart = new ListNode(0);
       pstart->next = head;
       head = head->next;
       pstart->next->next = nullptr; 
       while( head ){
           ListNode * temp = head;
           head = head->next;
           temp->next = nullptr;
           
           ListNode *pre = pstart;
           ListNode *pnext = pre->next;
           
           while(pnext && temp->val >= pnext->val){
               pre = pre->next;
               pnext = pnext->next;
           }
          
           pre->next = temp;
           temp->next = pnext;
           
        }
       
        head = pstart->next;
        delete pstart;
        return head;
    }
};
发表于 2017-08-18 22:45:00 回复(0)