LeetCode/147_Insertion_Sort_List at master · KnowledgeCenterYoutube/LeetCode · GitHub

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
Leetcode 147: Insertion Sort List
Detailed video explanation: https://youtu.be/CPAWcc78IB4
=====================================


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) {
        ListNode *start = new ListNode();
        start->next = head;
        ListNode *curr = head, *prev = start;
        while(curr){
            if(curr->next && (curr->next->val < curr->val)){
                // Insertion
                while(prev->next && (prev->next->val < curr->next->val))
                    prev = prev->next;
                ListNode *temp = prev->next;
                prev->next = curr->next;
                curr->next = curr->next->next;
                prev->next->next = temp;
                prev = start;
            } else
                curr = curr->next;
        }
        return start->next;
    }
};


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) {
        ListNode start = new ListNode();
        start.next = head;
        ListNode curr = head, prev = start;
        while(curr != null){
            if(curr.next != null && (curr.next.val < curr.val)){
                // Insertion
                while(prev.next != null && (prev.next.val < curr.next.val))
                    prev = prev.next;
                ListNode temp = prev.next;
                prev.next = curr.next;
                curr.next = curr.next.next;
                prev.next.next = temp;
                prev = start;
            } else
                curr = curr.next;
        }
        return start.next;
    }
}


Python3:
--------
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        start = ListNode()
        start.next = head
        curr, prev = head, start
        while curr != None:
            if curr.next != None and (curr.next.val < curr.val):
                # Insertion
                while prev.next != None and (prev.next.val < curr.next.val):
                    prev = prev.next
                temp = prev.next
                prev.next = curr.next
                curr.next = curr.next.next
                prev.next.next = temp
                prev = start
            else:
                curr = curr.next

        return start.next