博文中会简要介绍Leetcode P0147题目分析及解题思路。
“Insertion Sort List”是一道比较基础的插入排序的算法题。维护已经排好序的序列的两端指针，然后依次遍历剩余结点，每个结点通过比较找到插入的位置，最后执行插入即可。
Sort a linked list using insertion sort.
Algorithm of Insertion Sort:
- Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
- At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there.
- It repeats until no input elements remain.
以下是Java的题解代码实现。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode insertionSortList(ListNode head) {
if (head == null)
return head;
ListNode dummy = new ListNode(0, head);
ListNode left = dummy, right = head, curr = head.next;
while (curr != null) {
ListNode pos = left;
while (pos != right) {
if (pos.next.val >= curr.val)
break;
pos = pos.next;
}
// No one ahead is bigger than the current one
if (pos == right) {
right = right.next;
curr = curr.next;
}
else {
right.next = curr.next;
curr.next = pos.next;
pos.next = curr;
curr = right.next;
}
}
return dummy.next;
}
}
以下是C++的题解代码实现。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
if (!head)
return nullptr;
ListNode *dummy = new ListNode(0, head);
ListNode *left = dummy, *right = head, *curr = head->next;
while (curr) {
ListNode *pos = left;
while (pos != right) {
if (pos->next->val >= curr->val)
break;
pos = pos->next;
}
if (pos == right) {
right = right->next;
curr = curr->next;
}
else {
right->next = curr->next;
curr->next = pos->next;
pos->next = curr;
curr = right->next;
}
}
return dummy->next;
}
};