Wednesday, November 19, 2014

[LeetCode] Insertion Sort List

Sort a linked list using insertion sort.

思路:
拿出原list的头节点,用一个指针扫描新list直到找到插入位置,并插入。注意点:
1. 用dummy head来简化新list的头节点操作。
2. 由于插入节点需要依赖插入位置的前一节点。所以用指针p来查找新list节点时,始终用p->next来和要插入的节点比较,而不是用p来比较。
3. 注意当节点需要插入新list尾部的情况。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        ListNode *newHead = new ListNode(INT_MIN);
        while(head) {
            ListNode *cur = head;
            ListNode *p = newHead;
            head = head->next;
            while(p->next && p->next->val<=cur->val) 
                p = p->next;
            cur->next = p->next;
            p->next = cur;
        }
      
        head = newHead->next;
        delete newHead;
        return head;
    }
};

No comments:

Post a Comment