Discussion 7: Linked Lists

Solutions

Download Solution Code download
Exercise 1: The split() Method 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

/**
 * Splits the linked list starting at `head` into two halves. Returns the head of the second
 * half. If the list has an odd number of nodes, the extra node goes in the first half.
 */
static Node<Integer> split(Node<Integer> head) {
  Node<Integer> slow = head;
  Node<Integer> fast = head.next;

  while (fast.data != null) {
    fast = fast.next;
    if (fast.data != null) {
      fast = fast.next;
      slow = slow.next;
    }
  }

  Node<Integer> mid = slow.next;
  slow.next = new Node<>(null, null);

  return mid;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

/**
 * Splits the linked list starting at `head` into two halves. Returns the head of the second
 * half. If the list has an odd number of nodes, the extra node goes in the first half.
 */
static Node<Integer> split(Node<Integer> head) {
  Node<Integer> slow = head;
  Node<Integer> fast = head.next;

  while (fast.data != null) {
    fast = fast.next;
    if (fast.data != null) {
      fast = fast.next;
      slow = slow.next;
    }
  }

  Node<Integer> mid = slow.next;
  slow.next = new Node<>(null, null);

  return mid;
}
Trace through the split() method on the following example list:
(a)

For how many iterations will the while loop run? To which Nodes will fast and slow point at the end of each of these iterations?

The while loop will run for 2 iterations.
  • When we enter the loop, fast will point to the node containing 4 and slow will point to the node containing 1.
  • At the end of the first iteration, fast will point to the node containing 5 and slow will point to the node containing 4.
  • At the end of the second iteration, fast will point to the "empty" tail node and slow will point to the node containing 2.
(b)

Explain why this method works. How is it locating the midpoint of the list?

For every two "steps" that the fast pointer advances, the slow pointer advances only one step. Therefore, when the fast pointer reaches the end of the list, this will coincide with the slow pointer reaching the midpoint.
Exercise 2: The merge() Method
(a)

What local variables will we need to instantiate in order to merge head1 and head2 into a single list?

We'll create a new "empty" Node, merged, from which we will build our merged list; merged.next will be the head of the merged list. We also instantiate current, which tracks the tail of the merged list so that we can attach nodes from head1 and head2.
(b)

In the given example, should head1 or head2 become the head of the merged list? How do we determine this in general? After we choose the head, how do we decide which node to add next from the two lists as we continue building the merged list?

head1 should become the head, since head1.data <= head2.data. We'll always add the smaller head element to the merged lists (and using head1 in the case of equality to ensure stability of the sort). We update current.next so that it references head1, and then advance head1 = head1.next and current = current.next. We repeat this process with each head1 and head2 until we have completely traversed at least one of the lists.
(c)

In the given example, does head1 or head2 run out of nodes first? How can we attach all of the remaining nodes to the merged list?

head1 runs out of nodes first, since its largest element 4 is smaller than the largest element 5 of head2. After our while loop terminates, we check whether head1 or head2 is null. There will be at least one more node in the other list (in this case, head2) that is not yet merged, and we can attach these nodes to the merged list by setting current.next = head2.
(d)

What should we return at the end of the merge() method?

We should return merged.next, the head of the merged list.
(e)
Use your answers to complete the definition of the merge() method in IntLinkedList.java from the starter code. Use the provided tests to check that your implementation is correct. 
 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


/**
 * Returns the head of the merged list containing all nodes from the lists `head1` 
 * and `head2`, in sorted order. Requires that `head1` and `head2` are sorted.
 */
static Node<Integer> merge(Node<Integer> head1, Node<Integer> head2) {
  Node<Integer> merged = new Node<>(null, null); // "seed" node at the beginning
  Node<Integer> current = merged; // current position in merged list
  while (head1.data != null && head2.data != null) {
    if (head1.data <= head2.data) {
      current.next = head1;
      head1 = head1.next;
    } else {
      current.next = head2;
      head2 = head2.next;
    }
    current = current.next;
  }

  // attach any remaining nodes if one list is shorter than the other
  if (head1.data != null) {
    current.next = head1;
  }
  if (head2.data != null) {
    current.next = head2;
  }

  return merged.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


/**
 * Returns the head of the merged list containing all nodes from the lists `head1` 
 * and `head2`, in sorted order. Requires that `head1` and `head2` are sorted.
 */
static Node<Integer> merge(Node<Integer> head1, Node<Integer> head2) {
  Node<Integer> merged = new Node<>(null, null); // "seed" node at the beginning
  Node<Integer> current = merged; // current position in merged list
  while (head1.data != null && head2.data != null) {
    if (head1.data <= head2.data) {
      current.next = head1;
      head1 = head1.next;
    } else {
      current.next = head2;
      head2 = head2.next;
    }
    current = current.next;
  }

  // attach any remaining nodes if one list is shorter than the other
  if (head1.data != null) {
    current.next = head1;
  }
  if (head2.data != null) {
    current.next = head2;
  }

  return merged.next;
}
(f)

(Bonus Challenge): Implement the merge operation recursively by completing the mergeRecursive() method. What are the base and recursive cases?

There are two base cases: if head1 is empty, we return head2, and if head2 is empty, we return head1. Like the iterative implementation, we first compare head1.data with head2.data. If head1.data is smaller, we recurse by calling mergeRecursive(head1.next, head2), then return head1. Otherwise, we recurse with mergeRecursive(head1, head2.next) and return head2. 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


/**
 * Returns the head of the merged list containing all nodes from the lists `head1` 
 * and `head2`, in sorted order. Requires that `head1` and `head2` are sorted.
 */
static Node<Integer> mergeRecursive(Node<Integer> head1, Node<Integer> head2) {
  if (head1.data == null) {
    return head2;
  }
  if (head2.data == null) {
    return head1;
  }
  if (head1.data <= head2.data) {
    head1.next = mergeRecursive(head1.next, head2);
    return head1;
  } else {
    head2.next = mergeRecursive(head1, head2.next);
    return head2;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


/**
 * Returns the head of the merged list containing all nodes from the lists `head1` 
 * and `head2`, in sorted order. Requires that `head1` and `head2` are sorted.
 */
static Node<Integer> mergeRecursive(Node<Integer> head1, Node<Integer> head2) {
  if (head1.data == null) {
    return head2;
  }
  if (head2.data == null) {
    return head1;
  }
  if (head1.data <= head2.data) {
    head1.next = mergeRecursive(head1.next, head2);
    return head1;
  } else {
    head2.next = mergeRecursive(head1, head2.next);
    return head2;
  }
}
Exercise 3: The mergeSort() Method
Finally, it's time to put everything together: 
1
2
3
4
5

/**
 * Sorts this list using the Merge Sort algorithm. 
 * Returns the head of the sorted list.
 */ 
static void mergeSort(Node<Integer> head) { ... }

1
2
3
4
5

/**
 * Sorts this list using the Merge Sort algorithm. 
 * Returns the head of the sorted list.
 */ 
static void mergeSort(Node<Integer> head) { ... }
(a)

What are the base cases, and what should the method return?

If the list has size 0 or 1 (i.e., head.data == null or head.next.data == null), then it is trivially sorted, so we simply return head.
(b)

How can you use the split() and merge() helper methods to define the recursive step?

We first call split() to split the list in half and find its midpoint node. Next, we can recursively call mergeSort() on the left and right halves. Finally, we call merge() to combine the two sorted halves into a single sorted list and return the head of the merged list.
(c)
Use your answers to complete the definition of the mergeSort() method and use the provided tests to check that your implementation is correct. 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

/**
 * Sorts this list using the Merge Sort algorithm. 
 * Returns the head of the sorted list.
 */
private static Node<Integer> mergeSort(Node<Integer> head) {
  if (head.data == null || head.next.data == null) { // list has size 0 or 1
    return head; // already sorted
  }
  Node<Integer> mid = split(head);
  Node<Integer> sortedLeft = mergeSort(head); // sort left
  Node<Integer> sortedRight = mergeSort(mid); // sort right
  return merge(sortedLeft, sortedRight);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

/**
 * Sorts this list using the Merge Sort algorithm. 
 * Returns the head of the sorted list.
 */
private static Node<Integer> mergeSort(Node<Integer> head) {
  if (head.data == null || head.next.data == null) { // list has size 0 or 1
    return head; // already sorted
  }
  Node<Integer> mid = split(head);
  Node<Integer> sortedLeft = mergeSort(head); // sort left
  Node<Integer> sortedRight = mergeSort(mid); // sort right
  return merge(sortedLeft, sortedRight);
}
Exercise 4: Complexity Analysis
The time complexity of merge sort on linked lists follows the same breakdown as the array-based implementation, giving a total runtime of \(O(N \log N)\). However, the space complexity differs!

What is the space complexity of merge sort on linked lists, and why is it different from the array-based implementation?
(Hint: What dominates the space complexity in the latter?)
The space complexity of merge sort on linked lists is \(O(\log N)\). Each of the methods that we wrote allocated only \(O(1)\) memory, so the space complexity is dominated by the \(O(\log N)\) depth of the recursion. On the other hand, the array-based implementation requires \(O(N)\) space to allocate the temporary "work" array used during each call to merge().