Reverse a Singly Linked List

Rushil Patel — Tue, 06 Sep 2016 00:00:00 GMT

Problem Description

The task here is to write a function that will reverse a singly linked list. The function will take a node, the head of the linked list. The function should return the head of the reversed linked list.

Process

Im only going focus on the iterative solution mainly because this is a relatively easy problem. The hardest part is executing the reversal in the correct order.

Here is a basic Node class I defined for this problem.

public class Node {
   public int value;
   public Node next;

   public Node(int value) {
      this.value = value;
      next = null;
   }
}

So the idea here is to traverse the linked list from head to tail and simultaneously reverse the links. In other words while we travel through the linked list we will switch the next pointers so that they point to the previous node rather than the next.

We have to be careful, if we set the next pointer of a node in the wrong order we will end up detaching the node from the rest of the list. To work around this, we can save the current.next node into our next node to hold onto the reference. Then we set current.next to the previous node, this is in effect reversing the links between the nodes. And then finally we advance the current node by setting the current node to next, remember we saved current.next into next so we are good.

public Node reverse(Node head) {
   Node current = head;
   Node previous = null;
   Node next = null;

   while (current != null) {

      next = current.next;
      current.next = previous;

      previous = current;
      current = next;
   }
}

This solution will run in O(n) time and O(1) space.

Two Sum

Rushil Patel — Mon, 05 Sep 2016 00:00:00 GMT

This is my breakdown of the Two Sum problem. It can be found here on leetcode and a bunch of other websites.

Problem Description

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

Note: Allowed to assume that each input has exactly one solution.

Process

Bruteforce

The obvious and naive way is to bruteforce. The general idea would be to keep generating a pair of numbers from the array until we get one that sums to our target value.

In code it would look something like this

def two_sum(numbers, target):
   for i in range(0, len(numbers) - 1):
      for k in range(i + 1, len(numbers)):
         if numbers[i] + numbers[k] == target:
            return [i + 1, k + 1]
   return [None, None]

In the code above we start from the beginning of the list and check every pair of numbers moving towards the end of the list. Note, we are given a constraint index1 < index2 which is why the inner loop iterates from i + 1, this insures that one index is less than the other.

The code above will run in O(n^2) time with O(1) space. For a problem like this O(n^2) is pretty poor performance.

You may have noticed the code above doesn’t take advantage of the fact that the array is already sorted. We can do better!

Optimization #1

We know that the array is already sorted, with this knowledge we can cut down the number of iterations executed. If we traverse the loops in the same fashion as above but we only continue incrementing if the sum of the numbers is less than the target. Once we reach a sum that is greater than the target, we can guarentee on the current iteration the other pair of numbers will also be greater than the sum because the array is ordered in increasing order. Thus, we have cut out some of the iterations.

def two_sum(numbers, target):
   current_sum = 0
   for i in range(0, len(numbers) - 1):
      for k in range(i + 1, len(numbers)):
         current_sum = 0
         if current_sum == target:
            return [i + 1, k + 1]
         elif current_sum > target:
            break
         else:
            continue
   return [None, None]

The above code is still O(n^2) but because this code will run N^2 times if the target is the sum of the last two numbers. But on average case this code will perform better than the bruteforce above.

Optimization #2

Let’s really make use of the fact that the array is sorted. In this approach we use two pointers starting on each end and step towards the middle of the array. Have any clues? Hint: We can make the sum converge.

def two_sum(numbers, target):
   left = 0, right = len(numbers) - 1
   current_sum = 0
   while left < right:
   	  current_sum = numbers[left] + numbers[right]
      if current_sum > target:
         right -= 1
      elif current_sum < target:
         left += 1
      else
         return [left + 1, right + 1]
   return [None, None]

Since we we start on the ends of the array we begin by finding the sum of the maximun and minimum values of the array. Notice that as the right pointer moves from the end of the array towards the middle the values decrease. In contrast as the left pointer moves from the beginning of the array to the middle the values increase. So if we find the sum of our two numbers to be greater than the target our only option is to move in a direction that would decrease the sum, thus we move the right pointer towards the middle of the array. Similarily, if we find the sum of the two numbers to be less than the target then we increase the sum, by moving the left pointer towards the middle.

This solution has O(n) time complexity and O(1) space complexity.

Code and eventually Data

Reverse a Singly Linked List

Problem Description

Process

Two Sum

Problem Description

Process

Bruteforce

Optimization #1

Optimization #2