Skip to content

Commit c6cb058

Browse files
TonnyLTonnyL
committed
feat: 147. Insertion Sort List
1 parent ecc377d commit c6cb058

14 files changed

Lines changed: 405 additions & 1 deletion

File tree

‎Golang/InsertionSortList/InsertionSortList.go‎

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
package InsertionSortList
2+
3+
//Sort a linked list using insertion sort.
4+
//
5+
//Accepted.
6+
7+
type ListNode struct {
8+
Val int
9+
Next *ListNode
10+
}
11+
12+
func insertionSortList(head *ListNode) *ListNode {
13+
fakeHead := &ListNode{Val: 0,}
14+
15+
for ; head != nil; {
16+
pre := fakeHead
17+
18+
for ; pre.Next != nil && pre.Next.Val <= head.Val; {
19+
pre = pre.Next
20+
}
21+
22+
headNext := head.Next
23+
head.Next = pre.Next
24+
25+
pre.Next = head
26+
head = headNext
27+
}
28+
29+
return fakeHead.Next
30+
}

‎Golang/InsertionSortList/InsertionSortList_test.go‎

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
package InsertionSortList
2+
3+
import (
4+
"testing"
5+
"reflect"
6+
)
7+
8+
func TestInsertionSortList(t *testing.T) {
9+
10+
if insertionSortList(nil) == nil {
11+
t.Log("pass")
12+
} else {
13+
t.Error("failed")
14+
}
15+
16+
if reflect.DeepEqual(
17+
insertionSortList(&ListNode{
18+
Val: 1,
19+
}),
20+
&ListNode{
21+
Val: 1,
22+
}) {
23+
t.Log("pass")
24+
} else {
25+
t.Error("failed")
26+
}
27+
28+
if reflect.DeepEqual(
29+
insertionSortList(&ListNode{
30+
Val: 1,
31+
Next: &ListNode{
32+
Val: 0,
33+
},
34+
}),
35+
&ListNode{
36+
Val: 0,
37+
Next: &ListNode{
38+
Val: 1,
39+
},
40+
}) {
41+
t.Log("pass")
42+
} else {
43+
t.Error("failed")
44+
}
45+
46+
}

‎Java/src/InsertionSortList.java‎

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
/**
2+
* Sort a linked list using insertion sort.
3+
* <p>
4+
* Accepted.
5+
*/
6+
public class InsertionSortList {
7+
8+
public ListNode insertionSortList(ListNode head) {
9+
ListNode fakeHead = new ListNode(0);
10+
11+
while (head != null) {
12+
ListNode pre = fakeHead;
13+
14+
while (pre.next != null && pre.next.val <= head.val) {
15+
pre = pre.next;
16+
}
17+
18+
ListNode headNext = head.next;
19+
head.next = pre.next;
20+
21+
pre.next = head;
22+
head = headNext;
23+
}
24+
25+
return fakeHead.next;
26+
}
27+
28+
public static class ListNode {
29+
30+
int val;
31+
ListNode next;
32+
33+
ListNode(int x) {
34+
val = x;
35+
}
36+
37+
@Override
38+
public boolean equals(Object obj) {
39+
if (obj instanceof ListNode) {
40+
ListNode node = (ListNode) obj;
41+
return this.next == null && node.next == null || this.val == node.val && (this.next != null) && this.next.equals(node.next);
42+
}
43+
return false;
44+
}
45+
46+
}
47+
48+
}

‎Java/src/InsertionSortListTest.java‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
import org.junit.Assert;
2+
import org.junit.Test;
3+
4+
public class InsertionSortListTest {
5+
6+
@Test
7+
public void testInsertionSortList() {
8+
InsertionSortList i = new InsertionSortList();
9+
10+
Assert.assertNull(i.insertionSortList(null));
11+
12+
Assert.assertEquals(i.insertionSortList(new InsertionSortList.ListNode(1)), new InsertionSortList.ListNode(1));
13+
14+
InsertionSortList.ListNode node0 = new InsertionSortList.ListNode(1);
15+
node0.next = new InsertionSortList.ListNode(0);
16+
InsertionSortList.ListNode node1 = new InsertionSortList.ListNode(0);
17+
node1.next = new InsertionSortList.ListNode(1);
18+
Assert.assertEquals(i.insertionSortList(node0), node1);
19+
20+
}
21+
22+
}

‎JavaScript/src/InsertionSortList.js‎

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
/**
2+
* Sort a linked list using insertion sort.
3+
*
4+
* Accepted.
5+
*/
6+
7+
function ListNode(val) {
8+
this.val = val;
9+
this.next = null;
10+
}
11+
12+
/**
13+
* @param {ListNode} head
14+
* @return {ListNode}
15+
*/
16+
let insertionSortList = function (head) {
17+
let fakeHead = new ListNode(0);
18+
19+
while (head != null) {
20+
let pre = fakeHead;
21+
22+
while (pre.next != null && pre.next.val <= head.val) {
23+
pre = pre.next;
24+
}
25+
26+
let headNext = head.next;
27+
head.next = pre.next;
28+
29+
pre.next = head;
30+
head = headNext;
31+
}
32+
33+
return fakeHead.next;
34+
};
35+
36+
if (insertionSortList(null) == null) {
37+
console.log("pass")
38+
} else {
39+
console.error("failed")
40+
}
41+
42+
/*
43+
if (insertionSortList(new ListNode(1)) === new ListNode(1)) {
44+
console.log("pass")
45+
} else {
46+
console.error("failed")
47+
}
48+
49+
let node0 = new ListNode(1);
50+
node0.next = new ListNode(0);
51+
node1 = new ListNode(0);
52+
node1.next = new ListNode(1);
53+
if (insertionSortList(node0) === node1) {
54+
console.log("pass")
55+
} else {
56+
console.error("failed")
57+
}*/

‎Kotlin/src/InsertionSortList.kt‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
/**
2+
* Sort a linked list using insertion sort.
3+
*
4+
* Accepted.
5+
*/
6+
class InsertionSortList {
7+
8+
fun insertionSortList(head: ListNode?): ListNode? {
9+
var node = head
10+
val fakeHead = ListNode(0)
11+
12+
while (node != null) {
13+
var pre: ListNode? = fakeHead
14+
15+
while (pre?.next != null && pre.next?.`val`!! <= node.`val`) {
16+
pre = pre.next
17+
}
18+
19+
val headNext = node.next
20+
node.next = pre?.next
21+
22+
pre?.next = node
23+
node = headNext
24+
}
25+
26+
return fakeHead.next
27+
}
28+
29+
data class ListNode(
30+
var `val`: Int,
31+
var next: ListNode? = null
32+
)
33+
34+
}

‎Kotlin/src/InsertionSortListTest.kt‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
import org.junit.Assert
2+
import org.junit.Test
3+
4+
class InsertionSortListTest {
5+
6+
@Test
7+
fun testInsertionSortList() {
8+
val i = InsertionSortList()
9+
10+
Assert.assertNull(i.insertionSortList(null))
11+
12+
Assert.assertEquals(i.insertionSortList(InsertionSortList.ListNode(1)), InsertionSortList.ListNode(1))
13+
14+
Assert.assertEquals(i.insertionSortList(InsertionSortList.ListNode(1).apply {
15+
next = InsertionSortList.ListNode(0)
16+
}), InsertionSortList.ListNode(0).apply {
17+
next = InsertionSortList.ListNode(1)
18+
})
19+
20+
}
21+
22+
}

‎Python/InsertionSortList.py‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
# Sort a linked list using insertion sort.
2+
#
3+
# Python2 time limit exceeded. Python3 accepted.
4+
5+
6+
class InsertionSortList:
7+
def insertionSortList(self, head):
8+
"""
9+
:type head: ListNode
10+
:rtype: ListNode
11+
"""
12+
fakeHead = ListNode(0)
13+
while head is not None:
14+
pre = fakeHead
15+
16+
while pre.next is not None and pre.next.val <= head.val:
17+
pre = pre.next
18+
19+
headNext = head.next
20+
head.next = pre.next
21+
22+
pre.next = head
23+
head = headNext
24+
25+
return fakeHead.next
26+
27+
28+
class ListNode(object):
29+
30+
def __init__(self, x):
31+
self.val = x
32+
self.next = None
33+
34+
def __eq__(self, other):
35+
return self.val == other.val and self.next == other.next

‎Python/InsertionSortListTest.py‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
from unittest import TestCase
2+
3+
from InsertionSortList import InsertionSortList, ListNode
4+
5+
6+
class TestInsertionSortList(TestCase):
7+
def test_insertionSortList(self):
8+
ist = InsertionSortList()
9+
10+
self.assertIsNone(ist.insertionSortList(None))
11+
12+
self.assertEqual(ist.insertionSortList(ListNode(0)), ListNode(0))
13+
14+
node0 = ListNode(1)
15+
node0.next = ListNode(0)
16+
node1 = ListNode(0)
17+
node1.next = ListNode(1)
18+
self.assertEqual(ist.insertionSortList(node0), node1)

‎README.md‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,7 @@
22

33
My Solutions for LeetCode problems written in Go, Java, JavaScript, Kotlin, Python and Swift.
44

5-
Progress: **86 / 756**
5+
Progress: **87 / 756**
66

77
## Solutions
88
| # | Title | Go | Java | JavaScript | Kotlin | Python | Swift | Difficulty |
@@ -93,6 +93,7 @@ Progress: **86 / 756**
9393
| 137 | [Single Number II](https://leetcode.com/problems/single-number-ii/description/) | [√](Golang/SingleNumberII/SingleNumberII.go) | [√](Java/src/SingleNumberII.java) | [√](JavaScript/src/SingleNumberII.js) | [√](Kotlin/src/SingleNumberII.kt) | [√](Python/SingleNumberII.py) | [√](Swift/LeetCode/LeetCode/SingleNumberII.swift) | Medium |
9494
| 141 | [Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/description/) | [?](Golang/LinkedListCycle/LinkedListCycle.go) | [√](Java/src/LinkedListCycle.java) | [√](JavaScript/src/LinkedListCycle.js) | [?](Kotlin/src/LinkedListCycle.kt) | [√](Python/LinkedListCycle.py) | [?](Swift/LeetCode/LeetCode/LinkedListCycle.swift) | Easy |
9595
| 142 | [Linked List Cycle II](https://leetcode.com/problems/linked-list-cycle-ii/description/) | [?](Golang/LinkedListCycleII/LinkedListCycleII.go) | [√](Java/src/LinkedListCycleII.java) | [√](JavaScript/src/LinkedListCycleII.js) | [?](Kotlin/src/LinkedListCycleII.kt) | [√](Python/LinkedListCycleII.py) | [?](Swift/LeetCode/LeetCode/LinkedListCycleII.swift) | Medium |
96+
| 147 | [Insertion Sort List](https://leetcode.com/problems/insertion-sort-list/description/) | [√](Golang/InsertionSortList/InsertionSortList.go) | [√](Java/src/InsertionSortList.java) | [√](JavaScript/src/InsertionSortList.js) | [√](Kotlin/src/InsertionSortList.kt) | [√](Python/InsertionSortList.py) | [√](Swift/LeetCode/LeetCode/InsertionSortList.swift) | Medium |
9697

9798
## Contributions
9899
⚠️ Notice: We do **NOT** accept pull requests currently.

0 commit comments

Comments
 (0)