[LeetCode] Insertion Sort List

简介: Sort a linked list using insertion sort.解题思路 对于得到结点current的插入位置,从头结点开始遍历,直到遍历到值大于等于节点current的结点,然后将从该结点到current的前驱结点的所有结点的值依次和current结点的值交换,从而达到将该节点插入所遍历到的位置的目的。实现代码/****************

Sort a linked list using insertion sort.

  • 解题思路
    对于得到结点current的插入位置,从头结点开始遍历,直到遍历到值大于等于节点current的结点,然后将从该结点到current的前驱结点的所有结点的值依次和current结点的值交换,从而达到将该节点插入所遍历到的位置的目的。

  • 实现代码

/*****************************************************************
    *  @Author   : 楚兴
    *  @Date     : 2015/2/16 00:06
    *  @Status   : Accepted
    *  @Runtime  : 287 ms
******************************************************************/
#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}

};

class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        if (head == NULL || head->next == NULL)
        {
            return head;
        }
        ListNode *current = head->next;
        ListNode *temp;
        while(current != NULL)
        {
            temp = head;
            while(temp != current && temp->val < current->val)
            {
                temp = temp->next;
            }
            if (temp != current)
            {
                while (temp != current)
                {
                    swap(temp->val, current->val);
                    temp = temp->next;
                }
            }
            current = current->next;
        }
        return head;
    }
};

void print(ListNode *head)
{
    ListNode *tmp = head;
    while(tmp)
    {
        cout<<tmp->val<<" ";
        tmp = tmp->next;
    }
    cout<<endl;
}

int main()
{
    ListNode* head = new ListNode(12);
    ListNode* node1 = new ListNode(8);
    head->next = node1;
    ListNode* node2 = new ListNode(5);
    node1->next = node2;
    ListNode* node3 = new ListNode(9);
    node2->next = node3;
    ListNode* node4 = new ListNode(0);
    node3->next = node4;
    ListNode* node5 = new ListNode(1);
    node4->next = node5;
    ListNode* node6 = new ListNode(3);
    node5->next = node6;
    ListNode* node7= new ListNode(6);
    node6->next = node7;
    ListNode* node8 = new ListNode(4);
    node7->next = node8;
    print(head);

    Solution s;
    s.insertionSortList(head);
    print(head);
}

上述代码虽然已经被AC,但是用时还是太久,感觉主要是因为交换的次数太多了。故将代码更改如下:

/*****************************************************************
    *  @Author   : 楚兴
    *  @Date     : 2015/2/16 14:44
    *  @Status   : Accepted
    *  @Runtime  : 96 ms
******************************************************************/
class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        if (head == NULL || head->next == NULL)
        {
            return head;
        }

        ListNode *cur = head->next;  //当前结点
        ListNode *pre = head;  //当前结点的前驱结点
        ListNode *temp;
        ListNode *newcur;

        while(cur != NULL)
        {
            temp = head;
            newcur = cur->next;
            if (temp == head && temp->val > cur->val)  //头结点的值大于当前结点的值
            {
                pre->next = pre->next->next;
                cur->next = temp;
                head = cur;
                cur = newcur;
                continue;
            }

            //找到其后继结点的值不大于不大于当前结点值的temp结点
            while (temp->next != cur && temp->next->val < cur->val)
            {
                temp = temp->next;
            }

            if (temp->next != cur)
            {
                pre->next = pre->next->next;

                ListNode *t = temp->next;
                temp->next = cur;
                cur->next = t;
            }
            else
            {
                //位于当前结点之前的所有结点的值均小于当前结点
                pre = pre->next;
            }
            cur = newcur;
        }

        return head;
    }
};
目录
相关文章
|
7月前
|
Java
Leetcode 114. Flatten Binary Tree to Linked List
思路也很简单,先把root的左子树(如有)变成单链表 leftlinkedlist,把root的右子树(如有)变成单链表 rightlinkedlist,再把root的右节点变成leftlikedlist,再把rightlinkedlist接到leftlinkedlist后面,代码如下。
22 1
|
7月前
|
C++
Leetcode Copy List with Random Pointer(面试题推荐)
给大家推荐一道leetcode上的面试题,这道题的具体讲解在《剑指offer》的P149页有思路讲解,如果你手头有这本书,建议翻阅。
30 0
|
7月前
Leetcode 19.Remove Nth Node From End of List
删除单链表中的倒数第n个节点,链表中删除节点很简单,但这道题你得先知道要删除哪个节点。在我的解法中,我先采用计数的方式来确定删除第几个节点。另外我在头节点之前额外加了一个节点,这样是为了把删除头节点的特殊情况转换为一般情况,代码如下。
23 0
|
1月前
|
C++ 容器
【C++】STL容器——探究List与Vector在使用sort函数排序的区别(14)
【C++】STL容器——探究List与Vector在使用sort函数排序的区别(14)
|
1月前
|
大数据 Java 程序员
「LeetCode合集」链表(List)及经典问题
「LeetCode合集」链表(List)及经典问题
32 0
|
11月前
|
算法 C++
SGI-STL源码剖析之list::sort()
SGI-STL源码剖析之list::sort()
81 0
LeetCode 75 Sort Colors 颜色分类(荷兰国旗)
Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
72 0
LeetCode 141. 环形链表 Linked List Cycle
LeetCode 141. 环形链表 Linked List Cycle
|
5天前
|
存储 Java 测试技术
滚雪球学Java(57):解密Java中List接口底层实现原理
【6月更文挑战第11天】🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!
21 2
滚雪球学Java(57):解密Java中List接口底层实现原理
|
6天前
|
存储 安全 Java
Java集合详解:Set, Map, Vector, List的对比与联系
Java集合框架核心包括List、Set、Map和Vector。List允许重复元素,如ArrayList(适合读取)和LinkedList(适合插入删除)。Set不允许重复,有HashSet(无序)和TreeSet(排序)。Map存储键值对,HashMap(无序)和TreeMap(排序)。Vector是线程安全的ArrayList替代品,但在多线程环境下使用。选择集合类型应根据应用场景,如有序、无序、键值对需求及线程安全考虑。