[LeedCode OJ]#147 Insertion Sort List

作者:计算机教程

[LeedCode OJ]#21 Merge Two Sorted Lists

 

 

题意:

给定两个已经排好序的链表,现在要求把这两个链表归并成一个新的有序链表

 

思路:

由于两个链表都是有序的,所以我们只需要两个链表都从头结点开始,比较其结点中值的大小,每次选值较小的结点加入目标链表中。

 

 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution
{
 public:
  ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
  {
   ListNode *l3 = new ListNode(0);
   ListNode *newlist = l3;
   while(l1&&l2)
   {
    if(l1->val<=l2->val)
    {
     l3->next = l1;
     l1 = l1->next;
    }
    else
    {
     l3->next = l2;
     l2 = l2->next;
    }
    l3 = l3->next;
   }
   l3->next = l1?l1:l2;
   return newlist->next;
  }
};

 

 

http://www.bkjia.com/cjjc/1052169.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1052169.htmlTechArticle[LeedCode OJ]#21 Merge Two Sorted Lists 题意: 给定两个已经排好序的链表,现在要求把这两个链表归并成一个新的有序链表 思路: 由于两个链表都...

[LeedCode OJ]#147 Insertion Sort List

 

 

题意:

给定一个链表,要求使用插入排序返回一个排好序的链表

 

思路:

建立新的链表,按照插入排序的特点,每次循环新链表找到新结点将要插入的位置

 

 

/**
 * 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 *newlist = new ListNode(0);
   ListNode *cur = head;
   while(cur)
   {
    ListNode *ptr = newlist;
    ListNode *pnext = cur->next;
    while(ptr && ptr->next && ptr->next->valval)
    {
     ptr = ptr->next;
    }
    cur->next = ptr->next;
    ptr->next = cur;
    cur = pnext;
   }
   return newlist->next;
  }
};

 

 

http://www.bkjia.com/cjjc/1053396.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1053396.htmlTechArticle[LeedCode OJ]#147 Insertion Sort List 题意: 给定一个链表,要求使用插入排序返回一个排好序的链表 思路: 建立新的链表,按照插入排序的特点...

本文由nba买球发布,转载请注明来源

关键词: