Reference: LeetCode
Difficulty: Medium

My Post: [3ms] Java solution with comments (visual)

Problem

Sort a linked list using insertion sort.

Example: 

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

Analysis

Iteration

Original: 33 ms

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
public ListNode insertionSortList(ListNode head) {
  if (head == null || head.next == null) {
    return head;
  }
  
  ListNode dummy = new ListNode(-1);
  dummy.next = head;
  
  ListNode prev = dummy;
  ListNode curr = head;
  // 1    3    5    7    4    9
  //      p    p.n  pr   curr nT
  while (curr != null) {
    ListNode nextTemp = curr.next; // record the next node to proceed
    ListNode p = dummy;
    while (p.next != curr && p.next.val <= curr.val) {
      p = p.next;
    } // p.next stops at the node that is > curr.val

    if (p.next != curr) { // modify when p.next is not curr itself
      prev.next = curr.next; // remove
      curr.next = p.next; // add
      p.next = curr;
    } else {
      prev = curr; // if p.next == curr, we need to update prev
    }
    // update
    curr = nextTemp;
  }
  
  return dummy.next;
}

Improvement: 3 ms

Note:

  • prev != dummy is very important!!! Otherwise, dummy node would be compared.
  • Or set prev = head and curr = head.next.
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
public ListNode insertionSortList(ListNode head) {
  if (head == null || head.next == null) {
    return head;
  }
  
  ListNode dummy = new ListNode(-1);
  dummy.next = head;
  
  ListNode prev = dummy;
  ListNode curr = head;
  // 1    3    5    7    4    9
  //      p    p.n  pr   curr nT
  while (curr != null) {
    ListNode nextTemp = curr.next;
    ListNode p = dummy;
    
    if (prev != dummy && prev.val > curr.val) {
      while (p.next != curr && p.next.val <= curr.val) {
        p = p.next;
      } // p.next stops at the node that is > curr.val
      prev.next = curr.next; // remove
      curr.next = p.next; // add
      p.next = curr;
      // do not need to update prev 
    } else {
      prev = curr; // update prev, since curr is not modified
    }
    // update
    curr = nextTemp;
  }
  
  return dummy.next;
}

The version I wrote at the first time:

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
// dummy  3    4    1    5
//  t     t.n       p    p.n
//             prev
public ListNode insertionSortList(ListNode head) {
  if (head == null || head.next == null) { // size == 0 OR 1
    return head;
  }
  ListNode dummy = new ListNode(-1);
  dummy.next = head;
  ListNode p = head.next; // start from the second node
  ListNode prev = head;   // otherwise it would compare with dummy

  while (p != null) {
    ListNode t = dummy;

    if (prev.val > p.val) { // p needs swapping (better performance)
      while (t.next != p && p.val > t.next.val) {
        t = t.next;
      } // stops at the right position
      prev.next = p.next;
      p.next = t.next;
      t.next = p;
      p = prev.next; // set next (prev not changing)
    } else { // p needs not swapping
      prev = p;
      p = p.next;
    }
  }
  return dummy.next;
}

Time: $O(N^2)$
Space: $O(1)$