LeetCode147——對連結清單進行插入排序

我的LeetCode代碼倉：https://github.com/617076674/LeetCode

原題連結：https://leetcode-cn.com/problems/insertion-sort-list/description/

題目描述：

知識點：插入排序、連結清單

思路：用連結清單模拟插入排序的過程

為了避免對頭節點是否為null的讨論，設立虛拟頭節點dummyHead。

用cur指針周遊連結清單中的每一個節點，對每一個cur指針指向的位置，用newCur指針從頭開始周遊連結清單尋找cur指針指向的節點的合适的插入位置。由于需要交換節點的位置，我們需要記錄cur指針的前一個節點指針pre，以及newCur指針的前一個節點指針newPre。

時間複雜度是O(n ^ 2)，其中n為連結清單中的節點個數。空間複雜度是O(1)。

JAVA代碼：

public class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode pre = dummyHead;
        ListNode cur = dummyHead.next;
        ListNode newPre = dummyHead;
        ListNode newCur = dummyHead.next;
        while(cur != null) {
            while(newCur != cur && newCur.val < cur.val) {
                newPre = newPre.next;
                newCur = newCur.next;
            }
            if(newCur != cur) {
                ListNode nextCur = cur.next;
                newPre.next = cur;
                cur.next = newCur;
                pre.next = nextCur;
                cur = nextCur;
            }else {
                pre = pre.next;
                cur = cur.next;
            }
            newPre = dummyHead;
            newCur = dummyHead.next;
        }
        return dummyHead.next;
    }
}
           

LeetCode解題報告：