[数据结构与算法]Day1：Leetcode-19.Remove Nth Node From End of List

Tips:There is something noteworthy in C++ code，function getlen(LinkList * head)，this formal parameter?is fake，if we call this?funtion，our?actual parameter head will not change。That is different from array，for instance int fun(int a[])，it will change our actual parameter。?

Another one，if I write LinkList* head2 = head；If I change head2，it will not effect??head，or if I change head,it will not change head2 either.?

Solution 1:

? My First answer was?wrong? , I didn't??take this case into consideration.But the idea of?predecessor and?successor is not bad ，awesome，almost right.

?So I save the dommy node,do not operate the predecessor，that made a change.For this [1] case，we can not use head anymore，if head was moved，then we return head,there is no use,even we write cur -> next = null , it will not affect "head". That's the point.

Consider deletion of linklist。 We can imagin one roads，if we delete node "a"，"a" change the way。

class Solution {
public:
        int getlen(ListNode *head){
           int len = 0;
            while(head){
                len++;
                head = head->next;
            }
            return len;
        }

    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *head2 = head;
        int len = getlen(head);
        len = len - n + 1;
        ListNode *pre =new ListNode(0,head);
        ListNode *dommy = pre;
        ListNode *cur = head;
        for(int i = 1; i < len ;++i){
            pre = pre->next;
            cur = cur->next;
        }
        pre -> next = cur -> next;
        cur -> next = nullptr;
        return dommy->next;
    }
};

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeNthFromEnd(self, head, n):
        def getlen(head):
            length = 0;
            while head:
                length+=1
                head = head.next
            return length

        length = getlen(head)
        length = length - n + 1
        dummy =  ListNode(0,head)
        cur = dummy  
        for i in range(1,length):
            cur = cur.next
        cur.next = cur.next.next
        return dummy.next

?Solution 2

?We can use??two-pointer technique，when ed reach the end the position of st is the position to delete.?

class Solution {
public:
  
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *st  = new ListNode(0,head);
        ListNode *ed  = head;
        ListNode *dummy = st;

        for(int i=0;i<n;++i)
            ed = ed->next;

        while(ed){
            st = st->next;
            ed = ed->next;
        }
        st->next = st->next->next;
        
        return dummy->next;
    }
};

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0, head)
        stack = list()
        cur = dummy
        while cur:
            stack.append(cur)
            cur = cur.next
        
        for i in range(n):
            stack.pop()

        prev = stack[-1]
        prev.next = prev.next.next
        return dummy.next

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-b-61/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

?Solution 3

Stack , my favorite solution。Pay attention to python version ， prev = stack[-1] means，the last element，list is circular?

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0, head)
        first = head
        second = dummy
        for i in range(n):
            first = first.next

        while first:
            first = first.next
            second = second.next
        
        second.next = second.next.next
        return dummy.next

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-b-61/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        stack<ListNode*> stk;
        ListNode* cur = dummy;
        while (cur) {
            stk.push(cur);
            cur = cur->next;
        }
        for (int i = 0; i < n; ++i) {
            stk.pop();
        }
        ListNode* prev = stk.top();
        prev->next = prev->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-b-61/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。