# 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.headwhile 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? = nilvar tailSeeker = list.headvar count = 0while tailSeeker != nil {if count > n - 1 {if current == nil {current = list.head}current = current!.next}tailSeeker = tailSeeker!.nextcount += 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.headvar slow = list.headwhile fast != nil {fast = fast?.nextif fast != nil {fast = fast?.nextslow = 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 = 0var fast = list.headvar slow = list.headwhile fast != nil {fast = fast?.nextif 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.