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:
- Find the
sizeof the list
- Delete element from the list with "index"
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.
# 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
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!