Remove Nth Node From End of List


  • 0

    Click here to see the full article post


  • 0
    L
    This post is deleted!

  • 0
    T

    What kind of error message is threw?


  • 0
    L

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


  • 0
    N
    This post is deleted!

  • 1
    R

    The second solution is not "one pass", its actually a simultaneous double pass..
    So actually two passes.


  • 0
    I

    @romansky I think when we mean one-pass, 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 one-pass solution.


  • 0
    R

    @ironman7 I find that the number of times I traverse n members of a list the more acceptable meaning to "one-pass", as is mentioned in the body "one traversal", but is infact two pointers advancing in some-kind 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.


  • 0
    D

    Will given solution hit real-time error when calling removeNthFromEnd(NULL, 0) ??


  • 0
    S

    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


  • 0
    S
    232
    

    22
    1


  • 0
    S

    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
    

  • 0
    D

    don't even understand part of the explanation for the 2nd approach. What is D? and given n = 2, n+ 1 would be 3 which means the pointer should point at 4.


  • 0
    W

    Hi, D is dummy head (ListNode dummy in the program). Given n=2, n+1 would be 3, which means the pointer of first would move to next 3 times, starting from dummy head. It will point to 3 when the loop of "for" is finished


  • 0
    W

    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;
    }
    }


  • 0
    S

    With n > L / 2 second solution will not work


  • 0
    P

    I was wondering what should be the output if list just has 1 node and n = 1. In that case isn't the head node also 1st node of the list? LeetCode somehow is claiming the answer as wrong and expects nullptr as the answer. Can someone explain?


  • 0
    R

    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.


  • 0
    K

    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>n-1) result = result.next;
    else i++;
    tem = tem.next;
    }
    if(head.equals(result) && n != i) head = result.next;
    result.next = result.next.next;
    return head;

    }
    

    }


Log in to reply
 

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