Selection Sort List

Sort a linked list using selection sort.

Thoughts

每次从待排序的元素中选择最小的插入到已排好的最后面。由于还需要从未排好的中删除挑选出的元素，因此需要记录minPre。

Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode oIter = dummy, iIter = head; // the last of the sorted element, the iter of the elements needed to be searched  
        while (oIter != null && oIter.next != null) {
            iIter = oIter.next;
            ListNode pre = oIter;
            ListNode min = iIter, minPre = oIter;
            while (iIter != null) {
                if (iIter.val < min.val) {
                    min = iIter;
                    minPre = pre;
                }
                iIter = iIter.next;
                pre = pre.next;
            }
            minPre.next = minPre.next.next;

            ListNode tmp = oIter.next;
            oIter.next = min;
            min.next = tmp;
            oIter = oIter.next;
        }

        return dummy.next;
    }
}

Analysis

Errors: 1. minPrxe.nex t = minPre.next.next; 写在了后面，导致当只剩一个元素时会把加到排好序的最后一个元素删掉。

做题耗时17min 时间复杂度O(n^2), 空间O(1)。