LeetCode - Algorithms - 147. Insertion Sort List

Problem

147. Insertion Sort List

Java

enjoy algorithms

https://www.enjoyalgorithms.com/blog/sort-linked-list-using-insertion-sort

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
/**
 * 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 node = head;
        ListNode sortedHead = null;
        while (node != null) {
            ListNode nextNode = node.next;
            sortedHead = sortedInsert(sortedHead, node);
            node = nextNode;
        }
        return sortedHead;        
    }

    private ListNode sortedInsert(ListNode sortedHead, ListNode node) {
        if (sortedHead == null || sortedHead.val >= node.val) {
            node.next = sortedHead;
            return node;
        } else {
            ListNode temp = sortedHead;
            while (temp.next != null && temp.next.val < node.val) {
                temp = temp.next;
            }
            node.next = temp.next;
            temp.next = node;
        }
        return sortedHead;
    }
}

Submission Detail

  • Accepted
  • Runtime 18ms Beats 63.20% of users with Java
  • Memory 42.99mb Beats 90.09% of users with Java