19.Delete the countdown of the linked listNNode

topic：

Give you a linked list，Delete the countdown of the linked list n Node，And return to the head point of the linked list。

 

Exemplary example 1：

enter：head = [1,2,3,4,5], n = 2
Output：[1,2,3,5]

Exemplary example 2：

enter：head = [1], n = 1
Output：[]

Exemplary example 3：

enter：head = [1,2], n = 1
Output：[1]

 

hint：

• The number of nodes in the linked list is sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

 

Advance：Can you try to use a scanning implementation?？

Related Topics

Linked

Double pointer

👍 2500

👎 0

19.Delete the countdown of the linked listNNode.md

Thought：

It is definitely possible to solve the problem by taking dual traversal，但topic要求我们一次遍历解决问题，Then we have to diverge on our ideas。

我们可以设想假设设定了Double pointer p and q if，when q Pointed to the end NULL，p and q The number of elements separated from each other is n hour，Then delete p The next pointer completes the requirements。

Set up virtual nodes dummyHead direction head
设定Double pointer p and q，初始都direction虚拟节点 dummyHead
move q，until p and q The number of elements separated from each other is n
同hourmove p and q，until q direction的为 NULL
Will p 的下一Nodedirection下下Node

Code：

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummyHead = ListNode(val=0, next=head)
        head = tail = dummyHead
        for _ in range(n):
            tail = tail.next
        while tail.next is not None:
            head, tail = head.next, tail.next
        head.next = head.next.next
        return dummyHead.next

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *yummyNode = new ListNode(0);
        yummyNode->next = head;
        ListNode *fast = yummyNode;
        ListNode *slow = yummyNode;
        for(int i = 0; i < n; i++){
            slow = slow->next;
        }
        while (slow->next != nullptr){
            fast = fast->next;
            slow = slow->next;
        }
        //Recycling memory
        ListNode *del = fast->next;
        fast->next = del->next;
        delete del;
        //Return to node
        ListNode *ret = yummyNode->next;
        delete yummyNode;
        return ret;