Insertion Sort List

  • A+
所属分类:C语言
摘要

解题思路:
1.这个就是链表有序插入的变形
2.要设置4个指针,插入,查询,插入前,查询前指针

[摘要]本文是对Insertion Sort List的讲解,对学习C编程技术有所帮助,与大家分享。

解题思路:
1.这个就是链表有序插入的变形
2.要设置4个指针,插入,查询,插入前,查询前指针

 /**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     struct ListNode *next;
  * };
  */
 struct ListNode* insertionSortList(struct ListNode* head) {
     struct ListNode*  insert;
     struct ListNode*  insert_p;         
     struct ListNode*  cur;
     struct ListNode*  cur_p;
     int flag;
     if(head == NULL)
         return NULL;
     insert_p = head;
     insert = head->next;
     while(insert != NULL){
         cur = head;
         cur_p = head;
         flag = 0;
         while(cur != insert){
             if(head->val > insert->val){                                  //插入头结点,要注意交换次序
                 insert_p->next = insert->next;
                 insert->next = head;
                 head = insert;
                 insert = insert_p->next;
                 flag = 1;                 
                 break;
             }
             else if(cur->val > insert->val){
                 insert_p->next = insert->next;
                 cur_p->next = insert;
                 insert->next = cur;
                 insert = insert_p->next;
                 flag = 1;
                 break;
             }
             cur_p = cur;
             cur = cur->next;
         }
         if(flag == 0){                             //flag用来查看是否插入,插入的话insert已经移到下一个位置,就不用在移动了
             insert_p = insert;
             insert = insert->next;
         }
     }
     return head;
 }

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: