The Two-Pointer Technique in a Linked List

Two pointers moving in parallel

Consider the following problem:

Create a function that returns the nth last element of a singly linked list.

Notice how we are not asked to look for the nth element from the beginning but the nth element from the end. In order to do this, we need some way of knowing how far we are from the end of the list itself. However, in a singly linked list, there’s no easy way to iterate back through the list when you find the end, thus we’ll need to rely on something known as the two pointer technique. The two pointer technique allows us to keep two pointers referencing two different locations in the linked list. If we offset the pointers or increment them at different rates we can solve a lot of interesting problems which we can’t do with just one pointer.

The least efficient, non-pointer solution

To have a greater appreciation and understanding of the two-pointer technique and its efficiency, let’s take a quick look at a less optimal solution that might come to mind first.

One solution that might come to mind is to use an array to store a representation of the linked list. We can then simply return the node at the index from the end minus n.

  func getNodeFromLast(from list:LinkedList, at n:Int) -> Node? {
    var linkedListArray = [Node?]()
    var currentNode = list.head
    while currentNode != nil {
      linkedListArray.append(currentNode!)
      currentNode = currentNode!.next
    }
    return linkedListArray[linkedListArray.count - n];
  }

While this approach results in an easy-to-read implementation, it could also use up lots of memory maintaining a dual representation of the same data. If the linked list has one million nodes, we’ll need one million pointers in an array ArrayList to keep track of it! An approach like this results in an extra O(n) space being allocated.

The two pointer solution

Instead of creating an entirely parallel list, we can solve this problem by iterating with two pointers, one seeking the tail and the other lagging by the nth amount.

current = nil
tailSeeker = linked list head
count = 0

while tailSeeker is not nil
  if count > n - 1
    if current == nil
      current = linked list head
    move current pointer forward 
 
 move tail seeker forward
 increment count

return current

Solution

In Swift, we could implement the nth-last-node-finder function as such:

 func getNodeFromLast(from list:LinkedList, at n:Int) -> Node? {
    var current:Node? = nil
    var tailSeeker = list.head
    var count = 0
    while tailSeeker != nil {
      if count > n - 1 {
        if current == nil {
          current = list.head
        }
        current = current!.next
      }
      tailSeeker = tailSeeker!.next
      count += 1
    }
    return current
  }

By using this approach we are able to complete this problem efficiently, in O(n) time (we must iterate through the entire list once) and O(1) space complexity (we always use only three variables no matter what size the list is: two pointers and a counter).

Pointers at different speeds

Using two pointers moving offset but in parallel was a good solution to the previous problem. However, there are other problems where having two pointers moving in parallel wouldn’t be as useful. Let’s take a look at one of those problems and consider a new strategy that uses two pointers moving at different speeds.

Consider finding the middle node of a linked list.

As before, it’s possible to find a solution by iterating through the entire list, creating an array representation, and then returning the middle index. But also as before, this can potentially take up lots of extra space:

create array
while the linked list has not been fully iterated through
  append the current element onto an array
  move forward one node
return array[length / 2]

Approach: fast and slow pointers

Instead, we can use two pointers to move through the list. The first pointer takes two steps through the list for every one step that the second takes, so it iterates twice as fast.

fastPointer = list head
slowPointer = list head
while fastPointer is not nil
  move fastPointer forward
  if the end of the list has not been reached
    move fastPointer forward again
move slowPointer forward
return slowPointer

When the first pointer reaches the end of the list, the “slower” second pointer will be pointing to the middle element. Let’s visualize the steps of the algorithm:

Starting State

F
S
1  2  3  4  5  6  7

First Tick

      F
   S
1  2  3  4  5  6  7

Second Tick

            F
      S
1  2  3  4  5  6  7

Third Tick

                  F
         S
1  2  3  4  5  6  7

Final Tick

                     F
         S
1  2  3  4  5  6  7  nil

As long as we always move the fast pointer first and check to see that it is not nil before moving it and the slow pointer again, we’ll exit iteration at the proper time and have a reference to the middle node with the slow pointer.

Solution and alternatives

 func getMiddleNode(from list:LinkedList) -> Node? {
    var fast = list.head
    var slow = list.head
    
    while fast != nil {
      fast = fast?.next
      if fast != nil {
        fast = fast?.next
        slow = slow?.next
      }
    }
    return slow
  }

As with the nth-to-last solution, this solution has O(n) time complexity, and O(1) space complexity, since only two nodes are created no matter the size of the input list.

Half-Speed

Another equally valid solution is to move the fast pointer once with each loop iteration but only move the slow pointer every-other iteration:

func getMiddleNode(from list:LinkedList) -> Node? {
  var count = 0
  var fast = list.head
  var slow = list.head
    
  while fast != nil {
    fast = fast?.next
    if count % 2 != 0 {
      slow = slow?.next
    }
    count += 1
  }
  return slow
}

Wrap-up

Many linked list problems can be solved with the two-pointer technique. If it seems like a linked list problem requires keeping track of multiple positions or creating other data representations (such as using an array), consider whether two pointers iterating in parallel or at different speeds could help solve the problem efficiently.