我的LeetCode代码仓:https://github.com/617076674/LeetCode
原题链接:https://leetcode-cn.com/problems/insertion-sort-list/description/
题目描述:
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiAzNfRHLGZkRGZkRfJ3bs92YsYTMfVmepNHLykEVPhXTq1EeRpHW4Z0MMBjVtJWd0ckW65UbM5WOHJWa5kHT20ESjBjUIF2X0hXZ0xCMx81dvRWYoNHLrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdssmch1mclRXY39CXldWYtlWPzNXZj9mcw1ycz9WL49zZuBnL3UzN3IjMwMjM5ATMwkTMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
知识点:插入排序、链表
思路:用链表模拟插入排序的过程
为了避免对头节点是否为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解题报告: