# 2 pointers in python - detailed explanation with video

• Hi!

### Video explanation

This is deeply explained in this youtube video, but you can find the summary below

### Trivial, Broute-force solution

In order to remove `N`th element from the end of the list, we'd need to:

1. Find the `size` of the list
2. Delete element from the list with "index" `size-N`

### How to find the size of a linked list

Arrays have easy access to the length, and linked lists - don't. We'd have to iterate thru the list until the end, in order to find its length

### How to delete an element from a linked list?

Look at this representation of the linked list from example:

``````[next; val = '1']
+- [next; val = '2']
+- [next; val = '3']
+- [next; val = '4']
+- [next; val = '5']
+- None
``````

now, if we'd have to delete the node with value '3' (let's write it like `<'3'>`), then we'd have to rewire `<'2'>` to point to the element which goes after `<'3'>` (which we know is addressed as (<'3'>.next). Since `<'2'>` itself is `<'2'>.next`, then we'd have to do the following:

``````<'2'>.next = <'2'>.next.next
``````
``````[next; val = '1']
+- [next; val = '2']
|  [next; val = '3']
+------ [next; val = '4']
+- [next; val = '5']
+- None
``````

### More optimal solution with 2 pointers

Instead of doing 2 passes as in trivial approach, we can have 2 pointers, one following another, maintaining N elements distance between them. This way, when the heading pointer stops, follower will point to the previous element to the one which we have to delete, `<'2'>` as we called it before.

### Solution

``````# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None

class Solution(object):
"""
:type n: int
:rtype: ListNode
"""
for i in xrange(n):
return follower.next

follower = follower.next
follower.next = follower.next.next
``````

### Final thoughts

I hope that the video was not too boring and long, but I made it to explain the whole process of solving this task as if you were coding on a whiteboard. This can be helpful for those who goes to onsite interviews soon. Anyways, please, leave comments here or below the video if you have them - I'll answer and improve! Good luck!

• @3v3rgr33n Thanks！Great explaintion

• @xingjiu thank you. I'm doing google code jam videos now, stay tuned.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.