Skip to Content
Article

Two-Pointer Linked List Techniques

Learn how to approach Linked List problems with multiple iterator pointers.

Many common singly linked list problems can be solved by iterating with two pointers. This is sometimes known as the runner technique.

Two Pointers Moving in Parallel

Consider the following problem:

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

In order to do this, you’ll need some way of knowing how far you 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.

If you want, you can try your hand at the problem directly, or we can walk through some approaches below.

Approaches

One thing that might first come to mind is to use an ArrayList to store a representation of the linked list. 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 ArrayList to keep track of it! An approach like this results in an extra O(n) space being allocated.

public static Node arrayNthLast(LinkedList list, int n) { ArrayList<Node> linkedListArray = new ArrayList<Node>(); Node currentNode = list.head; while (currentNode != null) { linkedListArray.add(currentNode); currentNode = currentNode.getNextNode(); } return linkedListArray.get(linkedListArray.size() - n); }

Instead of creating an entire parallel list, we can solve this problem by using two pointers at different positions in the list but moving at the same rate. As in the previous example, we will use one pointer to iterate through the entire list, but we’ll also move a second pointer delayed n steps behind the first one.

current = null
tailSeeker = linked list head
count = 0

while tail pointer exists
  move tail pointer forward
  if count >= n
    set nthLastNodePointer to head if it's still null or move it forward
  increment count

return nthLastNodePointer

Implementation

Ready to Learn More?

Find the course that's right for you! Explore our catalog or get a recommendation.