LeetCode Insertion Sort List

LeetCode Insertion Sort List

Sort a linked list using insertion sort.


对一个链表进行插入排序。

简单题,每次从原链表中断一个节点下来,然后在新的有序链表中线性查找插入的位置。这里有个技巧,有可能链表的第一个节点很大,后续节点需要插入表头;也可能后续节点很大,需要插入表尾;还可能是不大不小,插入中间。情况比较多,为了方便统一代码形式,可以在新的有序链表的表头插入一个INT_MIN的最小节点,这样所有代码都统一了,也不容易出错。

完整代码如下:

class Solution {
public:
	ListNode* insertionSortList(ListNode* head) {
		if (head == NULL || head->next == NULL)return head;
		ListNode *newHead = new ListNode(INT_MIN);
		newHead->next = head;
		head = head->next;
		newHead->next->next = NULL;
		while (head) {
			ListNode *insertPos = newHead->next, *pre = newHead;
			while (insertPos&&insertPos->val < head->val) {
				insertPos = insertPos->next;
				pre = pre->next;
			}
			ListNode *tmp = head;
			head = head->next;
			tmp->next = insertPos;
			pre->next = tmp;
		}
		return newHead->next;
	}
};

本代码提交AC,用时59MS。

Leave a Reply

Your email address will not be published. Required fields are marked *