找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1867|回复: 4
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Insertion Sort List 】【刷题第一弹2014】

[复制链接]

11

主题

10

精华

641

积分

超级会员

Rank: 4

积分
641
发表于 10-24-2014 08:49 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 wenyuanhust 于 10-24-2014 01:15 AM 编辑

leetcode:https://oj.leetcode.com/problems/insertion-sort-list/
汇总帖:http://www.meetqun.com/forum.php?mod=viewthread&tid=703
1. 题目:
Sort a linked list using insertion sort.
2. 分析
采用递归方法,现将以cur->next为头结点的子链表排序,然后将cur插入已排序的链表的合适位置
3. 复杂度
时间复杂度O(n^2),由于需要n次递归,空间复杂度O(n)
4. 代码
  1. /**
  2. * Definition for singly-linked list.
  3. * struct ListNode {
  4. *     int val;
  5. *     ListNode *next;
  6. *     ListNode(int x) : val(x), next(NULL) {}
  7. * };
  8. */
  9. class Solution {
  10. public:
  11.     ListNode *insertionSortList(ListNode *head) {
  12.         if(head == nullptr || head->next == nullptr) return head;
  13.         
  14.         ListNode dummy(-1);
  15.         ListNode *prev = &dummy;
  16.         
  17.         ListNode *sort = insertionSortList(head->next);
  18.         
  19.         for(prev->next = sort; sort; prev = sort, sort = sort->next){
  20.             if(sort->val > head->val)
  21.                 break;
  22.         }
  23.         prev->next = head;
  24.         head->next = sort;
  25.         return dummy.next;
  26.     }
  27. };
复制代码
5. 相关题目:
Sort list

本帖被以下淘专辑推荐:

0

主题

0

精华

131

积分

资深会员

Rank: 2

积分
131
发表于 11-14-2014 01:35 PM | 显示全部楼层
思路: *                 需要注意的特殊情况
*                 1. linked list为empty或linked list中只有一个元素,则直接返回。

*                 此题相当于对linked list进行插入排序。大致思想就是,将n个元素的数列分为已有序和无序两个部分。每次处理就是将无序数列的
* 第一个元素与有序数列的元素从前往后逐个进行比较,找出插入位置并将该元素插入到有序数列的合适位置。传进来的参数就是无序数列的头
* 节点。我们首先将其头结点的值作为新的有序数列的第一个节点,之后循环访问无序数列并插入到有序数列中。在这个过程当中,有以下几个
* pointer在作用,首先是无序linked list上有个pointer1不断向前得到新的待排序的数,然后在有序linked list有个pointer2用于不断向前
* 与无序linked list上待排序数据进行比较获取到插入位置,最后在有序linked list上还有个比pointer2前一个位置的pointer3用于完成最后
* 的插入操作。每次插入完成后,注意更新这些pointer恢复到初始位置准备下一次遍历并插入。
*                 需要注意待插入的无序数据有可能是插在已排序数据的head之前;也有可能插入在已排序数据的末尾之后。

代码:
  1. /**
  2. * Definition for singly-linked list.
  3. * public class ListNode {
  4. *     int val;
  5. *     ListNode next;
  6. *     ListNode(int x) {
  7. *         val = x;
  8. *         next = null;
  9. *     }
  10. * }
  11. */
  12. public class Solution {
  13.     public ListNode insertionSortList(ListNode head) {
  14.         
  15.         if( head==null || head.next==null)
  16.                     return head;
  17.            
  18.             ListNode tempHead = new ListNode(head.val);
  19.             ListNode tempPoint = tempHead;
  20.             ListNode tempPrevPoint = null;
  21.             head = head.next;
  22.            
  23.             while( head!=null ){
  24.                     while(tempPoint!=null){
  25.                             if(tempPoint.val<head.val){
  26.                                     tempPrevPoint = tempPoint;
  27.                                     tempPoint = tempPoint.next;
  28.                                     continue;
  29.                             }else{
  30.                                     if(tempPrevPoint==null){
  31.                                             ListNode newTempHead = new ListNode(head.val);
  32.                                             newTempHead.next = tempHead;
  33.                                             tempHead = newTempHead;
  34.                                     }else{
  35.                                             ListNode newNode = new ListNode(head.val);
  36.                                             tempPrevPoint.next = newNode;
  37.                                             newNode.next = tempPoint;
  38.                                     }
  39.                                     break;
  40.                             }
  41.                     }
  42.                     if(tempPoint==null){
  43.                                 ListNode newNode = new ListNode(head.val);
  44.                                 tempPrevPoint.next = newNode;
  45.                     }
  46.                 tempPoint = tempHead;
  47.                 tempPrevPoint = null;
  48.                     head = head.next;
  49.             }
  50.    
  51.             return tempHead;
  52.     }
  53. }
复制代码

复杂度分析:Z, I) r: Z$ V. W; v
时间复杂度 ------ O(n^2), 空间复杂度 ------ O(n)

回复 支持 反对

使用道具 举报

18

主题

9

精华

522

积分

超级会员

Rank: 4

积分
522
发表于 12-20-2014 12:26 AM | 显示全部楼层
贴一个非递归的方法,指针p代表排好序的list里面的最后一个node, 注意需要判断新插入的node是不是排在整个有序list的末尾:
  1. class Solution {
  2. public:
  3.     ListNode *insertionSortList(ListNode *head) {
  4.         ListNode dummy(INT_MIN);
  5.         dummy.next = head;

  6.         for (ListNode *p = &dummy; p->next != nullptr;) {
  7.             auto pos = findInsertPos(&dummy, p->next, p->next->val);
  8.             if(pos->next == p->next ){
  9.                 p = p->next;
  10.             }else{
  11.             ListNode *tmp = p->next->next;
  12.             p->next->next = pos->next;
  13.             pos->next = p->next;
  14.             p->next = tmp;
  15.             }
  16.         }
  17.         return dummy.next;
  18.     }

  19.     ListNode* findInsertPos(ListNode *head, ListNode *last, int x) {
  20.         ListNode *pre = nullptr;
  21.         for (ListNode *cur = head; cur != last && cur->val <= x;
  22.              cur = cur->next)
  23.             pre = cur;
  24.         return pre;
  25.     }
  26. };
复制代码

复杂度分析  时间复杂度--------O(n^2), 空间复杂度-----O(1)
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表