LeetCode-学会对无序链表进行插入排序(详解)

前言

请坐

一、对无序链表进行插入排序题链接

题目描述

对链表进行插入排序。

插入排序算法：

1. 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
2. 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
3. 重复直到所有输入数据插入完为止。

测试样例1：

输入: 4->2->1->3
输出: 1->2->3->4

测试样例2：

输入: -1->5->3->4->0
输出: -1->0->3->4->5

题目思路

重排链表

1. 把第一个节点移除，且把这个节点的next置空，防止形成环形链表
2. 然后定义几个指针来进行操作，比较c和cur
3. 如果cur->val大于c->val,则c和p都进一,否则就开始排序
   如图:
   
4. 一 时刻注意newhead->val的值，要比较newhead->val的值和cur->val,如果newhead->val<=cur->val,则让newhead指向cur，保证newhead永远指向头节点。 二 还有另一种写法,观察规律,只有当p是NULL的时候才要改变newhead,所以可以用p是否为NULL来改变newhead.
   如图:
   
5. 也要判断p是否为NULL的时候，如果第一次比较，cur->val就小于c->val，则p无需变动。

注意：因为是无序的，所以要注意newhead的指向，要把newhead永远指向头节点.

这里有两种代码,风格不同

代码1

代码如下:这是不创建哨兵位的解法,当然这是在第二个循环内来进行插入

struct ListNode* insertionSortList(struct ListNode* head)
{
    
    if(head==NULL||head->next==NULL)
    {
    
        return head;
    }
    //1
    struct ListNode*newhead=head;
    struct ListNode*cur=head->next;
    newhead->next=NULL;

    //2
    while(cur)//终止条件
    {
    
        struct ListNode* next=cur->next;
        struct ListNode* c=newhead;
        struct ListNode* p=NULL;

        while(c)
        {
          
            if(cur->val<=c->val)
            {
    
                //判断头节点
                if(newhead->val>=cur->val)
                {
    
                    newhead=cur;
                }
                //判断p
                if(p!=NULL)
                {
    
                  p->next=cur;
                   
                }                                  
                cur->next=c;                
                break;               
            }
            else
            {
    
                p=c;
                c=c->next;
            }
            
        }

        if(c==NULL)
        {
    
            p->next=cur;
            cur->next=c;
            

        }

        cur=next;
        

    }
    
    return newhead;
}

代码2

代码如下:这是创建哨兵位的解法,当然这是是在第二个循环为来进行插入

typedef struct ListNode Node;
struct ListNode* insertionSortList(struct ListNode* head){
    
  if(head == NULL || head->next == NULL)
    return head;
  //创建排序链表
  Node* sortHead = (Node*)malloc(sizeof(Node));
  //头节点首先插入
  sortHead->next = head;
  head = head->next;
  sortHead->next->next = NULL;
  //插入剩余节点
  Node* cur = head;
  while(cur)
  {
    
    //首先保存next节点
    Node* next = cur->next;
 
    // 从排序链表的头开始，给待插入的节点找到一个合适的位置
    Node* sortPrev = sortHead;
    Node* sortCur = sortHead->next;
     
    while(sortCur)
    {
    
      if(cur->val > sortCur->val)
      {
    
        sortPrev = sortCur;
        sortCur = sortCur->next;
      }
      else
      {
    
        break;
      }
    }
    //在合适位置进行插入
    sortPrev->next = cur;
    cur->next = sortCur;
 
    cur = next;
  }
 
  Node* sortList = sortHead->next;
  free(sortHead);
 
  return sortList; 
}
 

总结

这个题就是要思考全面,然后有耐心的慢慢写