2 pointers in python - detailed explanation with video


  • 0

    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 Nth 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):
        def removeNthFromEnd(self, head, n):
            """
            :type head: ListNode
            :type n: int
            :rtype: ListNode
            """
            orighead = head
            follower = head
            for i in xrange(n):
                head = head.next
            if head is None:
                return follower.next
            
            while head.next is not None:
                head = head.next
                follower = follower.next
            follower.next = follower.next.next
            return orighead
    

    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!


  • 0
    X

    @3v3rgr33n Thanks!Great explaintion


  • 0

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


Log in to reply
 

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