題目描述:
對連結清單進行插入排序。
插入排序的動畫示範如上。從第一個元素開始,該連結清單可以被認為已經部分排序(用黑色表示)。
每次疊代時,從輸入資料中移除一個元素(用紅色表示),并原地将其插入到已排好序的連結清單中。
插入排序算法:
- 插入排序是疊代的,每次隻移動一個元素,直到所有元素可以形成一個有序的輸出清單。
- 每次疊代中,插入排序隻從輸入資料中移除一個待排序的元素,找到它在序列中适當的位置,并将其插入。
- 重複直到所有輸入資料插入完為止。
示例:
輸入:4 → 2 → 1 → 3
輸出:1 → 2 → 3 → 4
輸入:-1 → 5 → 3 → 4 → 0
輸出:-1 → 0 → 3 → 4 → 5
個人解法:
當連結清單為空或隻有一個節點時,直接傳回
将連結清單第一個節點的 next 置空,将這一部分看作有序連結清單,并從第二個節點開始,插入到前面有序連結清單的适當位置,對于适當位置的查找,從連結清單頭節點處開始周遊,用一前一後兩個指針儲存,後面的指針用于比較值大小,當值大小恰當時,前指針恰好為插入位置的前驅節點,将節點插入即可
由于将節點插入到有序連結清單中,該節點後面的節點便會丢失,故在插入前需要使用一個指針 next 指向待插入節點的後繼節點,而當周遊到連結清單的最後一個節點時,不需要再儲存該後繼節點
public ListNode insertionSortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode result = new ListNode(0, head);
ListNode cur = head.next;
ListNode next = cur.next;
head.next = null;
ListNode pre = result;
ListNode temp = head;
while (cur != null) {
if (temp != null && temp.val < cur.val) {
pre = pre.next;
temp = temp.next;
} else {
pre.next = cur;
cur.next = temp;
if (next == null) {
break;
}
cur = next;
next = cur.next;
pre = result;
temp = result.next;
}
}
return result.next;
}
官方解法:
對連結清單進行插入排序的具體過程如下。
- 首先判斷給定的連結清單是否為空,若為空,則不需要進行排序,直接傳回。
- 建立啞節點 dummyHead,令 dummyHead.next = head。引入啞節點是為了便于在 head 節點之前插入節點。
- 維護 lastSorted 為連結清單的已排序部分的最後一個節點,初始時 lastSorted = head。
- 維護 curr 為待插入的元素,初始時 curr = head.next。
- 比較 lastSorted 和 curr 的節點值。
- 若 lastSorted.val <= curr.val,說明 curr 應該位于 lastSorted 之後,将 lastSorted 後移一位,curr 變成新的 lastSorted。否則,從連結清單的頭節點開始往後周遊連結清單中的節點,尋找插入 curr 的位置。令 prev 為插入 curr 的位置的前一個節點,進行如下操作,完成對 curr 的插入:
- 令 curr = lastSorted.next,此時 curr 為下一個待插入的元素。
- 重複第 5、6、7 步,直到 curr 變成空,排序結束。
- 傳回 dummyHead.next,為排序後的連結清單的頭節點。
public ListNode insertionSortList1(ListNode head) {
if (head == null) {
return head;
}
ListNode dummy = new ListNode(0, head);
ListNode lastSorted = head, curr = head.next;
while (curr != null) {
if (lastSorted.val <= curr.val) {
lastSorted = lastSorted.next;
} else {
ListNode prev = dummy;
while (prev.next.val <= curr.val) {
prev = prev.next;
}
lastSorted.next = curr.next;
curr.next = prev.next;
prev.next = curr;
}
curr = lastSorted.next;
}
return dummy.next;
}