Insertion Sort List

Description

Sort a linked list using insertion sort.

Example
Given 1->3->2->0->null, return 0->1->2->3->null.

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: The head of linked list.
     */
    ListNode *insertionSortList(ListNode *head) {
        // write your code here
        // get a new dummy, then trying to append node
        if (!head) {
            return nullptr;
        }
        ListNode dummy(0);
        ListNode* search = &dummy;
        ListNode* cur = head;
        while (cur) {
            // search
            search = &dummy;
            while (search->next && search->next->val < cur->val) {
                search = search->next;
            }
            // place
            ListNode* tmp = search->next;
            ListNode* loopnext = cur->next;
            search->next = cur;
            cur->next = tmp;
            cur = loopnext;
        }
        return dummy.next;
    }
};

Similar problems

x

Tags

x