My one pass solution with two pointers


  • 7
    V
    class Solution:
    def removeNthFromEnd(self, head, n):
    	cur = head
    	npre= head
    	dis = 0
    	count = 1
    	while cur.next is not None:
    		cur = cur.next
    		count += 1
    		dis += 1
    		while dis > n:
    			npre = npre.next
    			dis -= 1
    	if count <= n:
    		return head.next
    	npre.next = npre.next.next
    	return head
    

    You should pay attention to the case which removes the first node.


  • 2
    Y

    this is a very smart method........


  • 2
    C

    Same idea but different way to handle removing head case:

    def removeNthFromEnd(self, head, n):
        slow = fast = head
        for i in range(n):
            fast = fast.next
        if fast is None:
            return head.next
        else:
            fast = fast.next
        while fast:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return head

  • 0
    C

    a little bit redundant, why not make inner loop as a if statement and remove dis-=1, that straightforward


  • 0
    J

    two pointers already mean two passes (instead of one pass as required), right?


  • 0
    S
    while dis > n
    

    could be simply changed to

    if dis > n
    

Log in to reply
 

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