147. Insertion Sort List

  • 32.2%

Sort a linked list using insertion sort.


方法一:

常规的插入排序,改成针对链表排序。

插入排序,每次从后向前走,这里每次从前向后走,找到插入位置。因为链表插入时O(1)空间,所以一样的。

我的代码实现:

Oct 11th, 2017

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
if(head==nullptr || head->next==nullptr)
return head;
ListNode* dummy = new ListNode(-1);
ListNode* p1 = head, *p2 = dummy, *p3;
while(p1!=nullptr){
p2 = dummy;
while(p2->next!=nullptr && p2->next->val <= p1->val){
p2 = p2->next;
}
p3 = p1->next;
p1->next = p2->next;
p2->next = p1;
p1 = p3;
}
return dummy->next;
}
};

my code

新建一个新节点,ListNode* dummy = new ListNode(0);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
if(head==NULL || head->next==NULL) return head;
ListNode* cur;
cur=head->next;

ListNode* dummy = new ListNode(0);
dummy->next = head;
head->next = NULL;
while(cur!=NULL){
ListNode* tmp = cur->next;
head = dummy;
while(head->next!=NULL && head->next->val < cur->val)
head = head->next;
cur->next = head->next;
head->next = cur;
cur = tmp;
}
return dummy->next;
}
};

https://discuss.leetcode.com/topic/8570/an-easy-and-clear-way-to-sort-o-1-space

An easy and clear way to sort ( O(1) space )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public ListNode insertionSortList(ListNode head) {
if( head == null ){
return head;
}

ListNode helper = new ListNode(0); //new starter of the sorted list
ListNode cur = head; //the node will be inserted
ListNode pre = helper; //insert node between pre and pre.next
ListNode next = null; //the next node will be inserted
//not the end of input list
while( cur != null ){
next = cur.next;
//find the right place to insert
while( pre.next != null && pre.next.val < cur.val ){
pre = pre.next;
}
//insert between pre and pre.next
cur.next = pre.next;
pre.next = cur;
pre = helper;
cur = next;
}

return helper.next;
}

https://discuss.leetcode.com/topic/14916/explained-c-solution-24ms

Explained C++ solution (24ms)

Well, life gets difficult pretty soon whenever the same operation on array is transferred to linked list.

First, a quick recap of insertion sort:

Start from the second element (simply a[1] in array and the annoying head -> next -> val in linked list), each time when we see a node with val smaller than its previous node, we scan from the head and find the position that the current node should be inserted. Since a node may be inserted before head, we create a new_head that points to head. The insertion operation, however, is a little easier for linked list.

Now comes the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution { 
public:
ListNode* insertionSortList(ListNode* head) {
ListNode* new_head = new ListNode(0);
new_head -> next = head;
ListNode* pre = new_head;
ListNode* cur = head;
while (cur) {
if (cur -> next && cur -> next -> val < cur -> val) {
while (pre -> next && pre -> next -> val < cur -> next -> val)
pre = pre -> next;
/* Insert cur -> next after pre.*/
ListNode* temp = pre -> next;
pre -> next = cur -> next;
cur -> next = cur -> next -> next;
pre -> next -> next = temp;
/* Move pre back to new_head. */
pre = new_head;
}
else cur = cur -> next;
}
ListNode* res = new_head -> next;
delete new_head;
return res;
}
};

https://discuss.leetcode.com/topic/1855/accepted-solution-using-java

Accepted Solution using JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode insertionSortList(ListNode head) {
ListNode helper=new ListNode(0);
ListNode pre=helper;
ListNode current=head;
while(current!=null) {
pre=helper;
while(pre.next!=null&&pre.next.val<current.val) {
pre=pre.next;
}
ListNode next=current.next;
current.next=pre.next;
pre.next=current;
current=next;
}
return helper.next;
}

https://discuss.leetcode.com/topic/4932/python-time-limit-is-too-tight

Python time limit is too tight

I have basically the same code in python and java (see below). python got TLE, but java was accepted. I propose to relax the python time limit a little bit.

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
# @param head, a ListNode
# @return a ListNode
def insertionSortList(self, head):
srt = None
while head:
node = head
head = head.next
node.next = None
srt = self.insertTo(srt, node)
return srt

def insertTo(self, head, node):
node.next = head
head = node
while node.next and node.val > node.next.val:
node.val, node.next.val = node.next.val, node.val
node = node.next
return head

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
public ListNode insertionSortList(ListNode head) {
ListNode srt = null;
while (head != null) {
ListNode node = head;
head = head.next;
node.next = null;
srt = insertTo(srt, node);
}
return srt;
}

public ListNode insertTo(ListNode head, ListNode node) {
node.next = head;
head = node;
while (node.next != null && node.val > node.next.val) {
node.val = node.val ^ node.next.val;
node.next.val = node.val ^ node.next.val;
node.val = node.val ^ node.next.val;
node = node.next;
}
return head;
}
}
谢谢你,可爱的朋友。