Wow! Haven’t made a blog post in awhile, shame on me. Let’s get back to business. I’m going to start a blog series on various different data structures and how to work with them. I find this to be a useful topic for things such as programming interviews and competitive programming.

In this first section, I’ll brainstorm some practical uses for the Linked List, and go over a couple common Linked List problems from Cracking the Coding Interview v5.

Why use Linked Lists?

Good question, when I first learned them I honestly saw no reason to ever use them. Fast forward to today, and I think they’re a fundamental data structure that you will likely use in nearly every project. Stacks and Queues are special types of Linked Lists and are very common.

Some practical examples of Linked Lists:

  • A deck of cards
  • Trains
  • A list of directions

And generally, we want to use Linked Lists when:

  • There are an unknown # of items
  • You need the ability to re-arrange, insert, and delete in various different locations.

Linked Lists are very good at insertion and deletion, having a worst case time complexity of O(1) for both.

Next I’ll go over some common algorithms you will implement when using a Linked List.

Problem 1

Remove duplicates from an unsorted Linked List.

Deletion is a strength of the Linked List, so it’s important to know how to implement it. Why implement your own when most Linked List classes will include it? Well, I think it’s nice to know how and why some things work, instead of blindly using a provided method. Also, code interviews.

Anyway, it sounds pretty simple, and it is, but if you haven’t worked with Linked Lists in awhile then it’s easy to forget.

Solution

First thing’s first, if a null value is passed, then we will want to instantly return because we can’t delete something from an empty list.

	public static void deleteDuplicates(LinkedListNode head) {
		if (head == null)
			return;
	}

Let’s discuss how we properly delete. Deletion is achieved in a Linked List by changing the next value of a node. So if we have 1->2->3, then we simply set the next value of 1 to 3, which leaves us with 1->3.

In this problem, we want to delete all the duplicates, so we will need iterate the list in two separate loops. Both loops terminate when the node pointer reaches the end of the list, which is when the next value is equal to null. The structure will look something like:

public static void deleteDuplicates(LinkedListNode head) {
  if (head == null)
    return;

LinkedListNode curr = head;
    while (curr != null) {
      LinkedListNode runner = curr;

      while (runner.next != null) {

      }
      curr = curr.next;
    }
}

We will be using the concept of a runner. The runner is simply a pointer that moves through the Linked List at a different pace from the original pointer. The purpose of the pointer is that it allows us to freely move through the Linked List within the inner loop, while maintaining our outer loop pointer for comparisons. This is just a standard nested loop, but modified for Linked List traversal.

And honestly… that might be the hardest part. All we need to do now is apply what I wrote previously about implementing deletion.

public static void deleteDuplicates(LinkedListNode head) {
  if (head == null)
    return;

  LinkedListNode curr = head;
  while (curr != null) {
    LinkedListNode runner = curr;

    while (runner.next != null) {
      if (runner.next.data == curr.data) {
        runner.next = runner.next.next;
      } else { // no duplicate --- continue
        runner = runner.next;
      }
    }
    curr = curr.next;
  }

}

Breaking this down:

  1. We use two loops to iterate the list. The first loop moves to the next node after the second loop iterates the entire list, which gives us coverage for our duplicate comparisons.
  2. If a duplicate is found then we set the node’s next value to the node’s next,next value, which essentially gives us deletion. Else, move to the next node in our runner pointer.
  3. Move the the curr pointer to the next node each time the first loop completes.

Tests

I: 1->1->0->1->1->3->2->0->0->1->1->2->3->2->0->2->0->1->3->2->0->3->1->0->0
O: 1->0->3->2

I: 1->3->3->4->3->4->1->3->4->1->5->2->5->4->5
O: 1->3->4->5->2

That was a nice warmup, so let’s do something a little more complex:

Problem 2

Given two numbers represented by two lists, write a function that returns sum list. The sum list is list representation of addition of two input numbers. The result will not be in reverse order.

Example

Input:
First List: 5->6->3 // represents number 365
Second List: 8->4->2 // represents number 248
Output
Resultant list: 6->1->3 // represents number 613

Solution

This is a painful problem because my intuitive solution involves a lot of conversions.

I have broken the problem down into these steps:

  1. Create a runner pointer that will fill the Linked List, and a head pointer which will be the value returned.
  2. Convert both lists to Strings.
  3. Reverse both Strings.
  4. Convert the Strings to ints, and sum them.
  5. Convert the resulting int back into a String.
  6. Store the first value of the String as an int in the head of the Linked List.
  7. Loop through the remainder of the String (using the runner pointer), appending the rest of the digits.
  8. Return head pointer.

What a royal pain… here we go. I’ll start by initializing some variables, and converting the lists to Strings. This can be achieved by iterating through the Linked Lists and storing the values.

public static LinkedListNode addLinkedLists(LinkedListNode a, LinkedListNode b) {

if (a == null || b == null) {
  return;
}

  String num1 = String.valueOf(a.data);
  String num2 = String.valueOf(b.data);
  LinkedListNode c = new LinkedListNode();
  LinkedListNode head = c;
  int sum = 0;
      
  while (a.next != null) {
    num1 += a.next.data;
    a = a.next;
  }
  
  while (b.next != null) {
    num2 += b.next.data;
    b = b.next;
  }

The problem states that the values are actually in reverse order, so the next step is to reverse both strings, sum them as ints, and convert back to String. YAY conversions. I’ll use StringBuilder to do the reversing, although the manual method of using a char array would work too.

public static LinkedListNode addLinkedLists(LinkedListNode a, LinkedListNode b) {
  String num1 = String.valueOf(a.data);
  String num2 = String.valueOf(b.data);
  LinkedListNode c = new LinkedListNode();
  LinkedListNode head = c;
  int sum = 0;
      
  while (a.next != null) {
    num1 += a.next.data;
    a = a.next;
  }
  
  while (b.next != null) {
    num2 += b.next.data;
    b = b.next;
  }

  StringBuilder reversedNumber = new StringBuilder(num1).reverse();
  int reversedA = Integer.parseInt(reversedNumber.toString());
  reversedNumber.setLength(0); // clear the string builder
  int reversedB = Integer.parseInt(reversedNumber.append(num2).reverse().toString());
  
  sum = reversedA + reversedB;
  String sumString = String.valueOf(sum);
  System.out.println("Sum = " + sumString);

One caveat is to remember to convert the StringBuilder objects back into Strings before using parseInt(). Now that we FINALLY have our sum in a nice String format, we need to convert the digits of this String into a Linked List. I’ll accomplish this by looping through the indices of the String.

public static LinkedListNode addLinkedLists(LinkedListNode a, LinkedListNode b) {
  String num1 = String.valueOf(a.data);
  String num2 = String.valueOf(b.data);
  LinkedListNode c = new LinkedListNode();
  LinkedListNode head = c;
  int sum = 0;
      
  while (a.next != null) {
    num1 += a.next.data;
    a = a.next;
  }
  
  while (b.next != null) {
    num2 += b.next.data;
    b = b.next;
  }

  StringBuilder reversedNumber = new StringBuilder(num1).reverse();
  int reversedA = Integer.parseInt(reversedNumber.toString());
  reversedNumber.setLength(0); // clear the string builder
  int reversedB = Integer.parseInt(reversedNumber.append(num2).reverse().toString());
  
  sum = reversedA + reversedB;
  String sumString = String.valueOf(sum);
  System.out.println("Sum = " + sumString);

  c.data = Character.getNumericValue(sumString.charAt(0));
  for (int i = 1; i <= sumString.length()-1; i++ ) {
    c.setNext(new LinkedListNode(Character.getNumericValue(sumString.charAt(i)), null, null));
    c = c.next;
  }
  return head;

One thing worth mentioning is that before the loop starts, we need to store the first value. This is because we will be setting the next values of our Linked List, which does not cover the first value.

Tests

t1 t2

Phew.. that wasn’t so bad aside but it’s a bit messy with all these conversions. Do I think it’s a good solution? Well, it could definitely be better.

Thanks for reading.