Insertion Sort List

https://leetcode.com/problems/insertion-sort-list/description/

Sort a linked list using insertion sort.

Thoughts

1. 插入排序是当前元素前已经排好，把当前元素往前插入到合适位置.

2. dummy用于指示已排好的list从哪开始。这里的dummy.next不要初始化成head.

3. 外循环一个指针next指向待排序的元素，初始化成next；内循环一个指针iter从dummy开始往后遍历，iter停在比next小但iter.next比next的位置，即要插入的位置。当next比所有已排好的都大时，意味着next位置其实不用动，iter会停在next位置前。

Code

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode dummy(-1);
        auto *d = &dummy, *next = head;
        while (next != NULL) {
            auto iter = d, next_next = next->next;
            while (iter->next != NULL && iter->next->val < next->val) {
                iter = iter->next;
            }
            next->next = iter->next;
            iter->next = next;
            next = next_next;
        }

        return d->next;
    }
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        ListNode oIter = head, iIter = dummy;
        while (oIter != null) {
            iIter = dummy;
            ListNode oIterNext = oIter.next;
            //oIter.next = null;
            while (iIter.next != null &&  iIter.next.val < oIter.val) {
                iIter = iIter.next;
            }

            oIter.next = iIter.next;
            iIter.next = oIter;
            oIter = oIterNext;
        }

        return dummy.next;
    }
}

Analysis

做题耗时: 1hour

Errors:

1. 让 dummy.next = head; 导致排好序的没排好序的连在了一起， 逻辑混乱不清。

时间复杂O(n^2).