# 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)。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/linked_list/selection-sort-list.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.