[LeetCode] 147. Insertion Sort List

Posted on | In

Problem

Sort a linked list using insertion sort.

147. Insertion Sort List

A graphical example of insertion sort. The partial sorted list (black) initially contains only the first element in the list. With each iteration one element (red) is removed from the input data and inserted in-place into the sorted list

Algorithm of Insertion Sort:

  1. Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
  2. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there.
  3. It repeats until no input elements remain.

Example 1:

1
2
Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

1
2
Input: -1->5->3->4->0
Output: -1->0->3->4->5

Explanation

  1. First create a dummy node, and we need to have a cur pointer points at the dummy node, and lstPtr pointer points at the original list’s node for iterating.

  2. While lstPtr is not null, we starts from lstPtr’s node, compare it with every cur.next’s node in the dummy list starts from the beginning of dummy list, here we also need a while loop to achieve this. If cur.next is null, or cur.next’s value is greater than lstPtr’s value, then we break out this inner while loop, and add lstPtr’s node to our dummy list.

Solution

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(-1);
        ListNode lstPtr = head;

        while (lstPtr != null) {
            ListNode cur = dummy;
            ListNode temp = lstPtr.next;
            while (cur.next != null && cur.next.val <= lstPtr.val) {
                cur = cur.next;
            }
            lstPtr.next = cur.next;
            cur.next = lstPtr;
            lstPtr = temp;
        }

        return dummy.next;
    }
}