Leetcode 19: Delete a linked list Delete the penultimate node of the linked list. Using the double pointer + GIF way to analyze, for your reference, I hope to help you.

Delete the NTH node from the list

Given a linked list, delete the NTH node from the bottom of the list and return the head of the list.

Advanced: Can you try using a scan implementation?



Their thinking

To delete a node nodeB from the linked list, nodeA must be found before the node, and then nodeA must be pointed to nodeC, the next node of nodeB, to achieve the deletion of node nodeB.

For example, to delete the node whose median value is 3 in linked list L(1->2->3->4->5), the previous node (the node whose median value is 2) of the node must be found before the node can be deleted, as shown below:


The title requires that the penultimate NTH node be deleted, so the previous node of this node should be found first. However, since the length of the whole linked list is not known, so the node to be deleted is not known which node is the positive number, so it is difficult to delete this node from the beginning.

Thinking a

First go through the linked list, get the length of the whole list; Assuming that the length of the entire list is L, it can be known that the node to be deleted is the l-N + 1 node. Go through it again and delete the NTH to last node. For example, if list L is 1->2->3->4->5 and n = 3, the node to be deleted is 5-3 + 1 = 3.

Idea 2

Although the idea is feasible, the linked list needs to be traversed twice, which is not simple enough. In addition, it is also mentioned in the progression of the topic to try to use a scan to achieve, so this paper adopts the two-pointer strategy to delete the penultimate NTH node through a scan.

In the last issue of linked list related topic virtual head node second kill linked list, the strategy of adding virtual head nodes was mentioned to solve the linked list problem. The advantage of adding virtual head nodes is that there is no need to consider the head nodes separately, so that the head nodes are treated just like other nodes. This paper also adopts this strategy.

For chestnut

List 1->2->3->4->5, n = 3 as chestnut, as shown below.


According to the above analysis, we need to findThe preceding node of the third to last node, that is, the node with the value 2;

increaseVirtual head node

The node whose value is 2 isFourth from last node (back to front)Add two Pointers fast/slow, pointing to the last element (NULL) and target.

At this point, the spacing between fast and slow is fixed (n = 3). After finding target(slow), you only need to delete the next node. But how to determine how many nodes are in front of the node pointed by slow?

Since it is currently known that the length between nodes pointing to fast and slow is fixed, it is only necessary to move these two Pointers forward until slow moves to the position of the virtual head node (value 0), at which point FAST points to the position of the node with value 4. Fast only needs to move the position of the virtual head node to the right by n + 1 = 4. As shown below:


When fast moves right to the node with the value 4, the Pointers slow and FAST move right at the same time until FAST moves to NULL, at which point slow moves rightThe target locationThat points to theThe NTH plus one node, as shown below.

Show me the Code

c++

ListNode* removeNthFromEnd(ListNode* head, int n) {

    ListNode* dummyHead = new ListNode(0);

    dummyHead->next = head;

    ListNode *slow = dummyHead, *fast = dummyHead;

    for (int i = 0; i < n + 1; ++i) {

        fast = fast->next;

    }



    while(fast ! = NULL) {

        slow = slow->next;

        fast = fast->next;

    }



    ListNode* delNode = slow->next;

    slow->next = delNode->next;

    delete delNode;



    ListNode* retNode = dummyHead->next;

    delete dummyHead;



    return retNode;

}

Copy the code

java

ListNode removeNthFromEnd(ListNode head, int n) {

    ListNode dummyHead = new ListNode(0);

    dummyHead.next = head;

    ListNode slow = dummyHead, fast = dummyHead;

    for (int i = 0; i < n + 1; ++i) {

        fast = fast.next;

    }



    while(fast ! = null) {

        slow = slow.next;

        fast = fast.next;

    }



    slow.next = slow.next.next;

    return dummyHead.next;

}

Copy the code

Highlights from the past

The virtual head node seconds kill linked list problem

Circular lists of single lists

Four ways to solve leetcode203. Remove linked list elements

83. Delete duplicate elements from the sorted list

Interviews cannot be reversed without a single – linked list

More wonderful

Pay attention to the public number [programmer Bear], background reply [algorithm] or [Python], you can get high-definition non-code classical algorithm or Python ebook ~

In order to reward readers, this public account will have gifts from time to time, please pay attention to ~