[LeetCode] Insertion Sort List

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;
    }
};