首页 > 其他 > 详细

【leetcode】Insertion Sort List (middle)

时间:2015-01-18 19:42:53      阅读:265      评论:0      收藏:0      [点我收藏+]

Sort a linked list using insertion sort.

 

思路:

用插入排序对链表排序。插入排序是指每次在一个排好序的链表中插入一个新的值。

注意:把排好序的部分和未排序的部分完全分开,指针不要有交叉。 即不会通过->next 重叠

class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        if(head == NULL)
            return NULL;

        ListNode * ans = head;
        head = head->next;
        ans->next = NULL; //排好序的第一个结点,后面跟的要是NULL 排好序的部分和未排好序的部分不能重合
        while(head != NULL) //还有要插入的 每次都把剩下还未排序部分的头结点插入
        {
            ListNode * pans = ans; //记录插入的位置
            ListNode * tmp = NULL; //交换时用的临时的值
            if(pans->val >= head->val) //新来的结点最小,是新的头结点
            {
                tmp = head;
                head = head->next;
                tmp->next = pans;
                ans = tmp;
                continue;
            }
            //找到要插入的前一个指针
            while(!(pans->val < head->val && (pans->next == NULL || pans->next->val >= head->val))) //比当前结点大,且小于等于后面的结点值,或后面的结点值为0
            {
                pans = pans->next;
            }
            tmp = head;
            head = head->next;
            tmp->next = pans->next;
            pans->next = tmp;
        }
        return ans;
    }
};

 

【leetcode】Insertion Sort List (middle)

原文:http://www.cnblogs.com/dplearning/p/4232131.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!