Remove Nth Node From End of List


@twittidai Thank you.But I think I have sloved the problem and it's because another method's error.

@romansky I think when we mean onepass, it means that the list is completely traversed.Since in the second solution, since the list is traversed in complete only once, it is referred as a onepass solution.

@ironman7 I find that the number of times I traverse n members of a list the more acceptable meaning to "onepass", as is mentioned in the body "one traversal", but is infact two pointers advancing in somekind of tandem.
I could (somewhat) understand if you were to invoke multiple functions for the same member while traversing (and by this possibly save some pointer lookups) but this is not the case.

As other people said, the second method is 'simultaneous two pass'. For exactly one pass, I can use a (n + 1)length buffer which stores the pointer.
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
header = head
buffer = (n + 1) * [0]
i = 0
while head:
buffer[i] = head
head = head.next
i += 1
i = i%(n + 1)
if buffer[i] == 0 :
return buffer[0].next
else:
buffer[i].next = buffer[i].next.next
return header

As other people said, the second method is 'simultaneous two pass'. For exactly one pass, I can use a (n + 1)length buffer which stores the pointer.
Here is my code:class Solution(object): def removeNthFromEnd(self, head, n): """ :type head: ListNode :type n: int :rtype: ListNode """ header = head buffer = (n + 1) * [0] i = 0 while head: buffer[i] = head head = head.next i += 1 i = i%(n + 1) if buffer[i] == 0 : return buffer[0].next else: buffer[i].next = buffer[i].next.next return header

Also, there is one corner case ( n > total length (including dummy head)) which the program of solution 2 can not cover, as :
// Advances first pointer so that the gap between first and second is n nodes apart
for (int i = 1; i <= n + 1; i++) {
first = first.next;
}The code above would run into NullPointerException if n > length of the list (including dummy head), it can be updated to:
for (int i = 1; i <= n+1; i++) { // do "move to next" from dummyHead (n + 1) times
fast = fast.next;
if (fast == null && i != n+1) { // fast == null && i == n+1 means you would like to delete the last node
return head;
}
}

For the corner case in the one pass, here's a solution where you do not need to store a buffer:
ListNode* removeNthFromEnd(ListNode* head, int n) { // If it's a single element, return NULL. if (head>next == NULL) return NULL; ListNode* p1 = head; ListNode* p2 = head; while(p2>next != NULL && n) p2 = p2>next; // After the above while loop, we might still have some n left // if the p2 reaches end quickly. We need to consider the case // when n > length of list. while(p2>next != NULL) { p1 = p1>next; p2 = p2>next; } // This is the case when n is left if (n > 0) { *p1 = *(p1>next); } else { p1>next = p1>next>next; } return head; }
This is O(n) without extra space.

public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode result = head;
if (result.next == null)
return null;
int i = 0;
ListNode tem = head;
while(tem.next != null){
if(i>n1) result = result.next;
else i++;
tem = tem.next;
}
if(head.equals(result) && n != i) head = result.next;
result.next = result.next.next;
return head;}
}