This is the 17th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

leetcode Delete the penultimate node of the linked list

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

Example 1:

Input: head = [1,2,3,4,5], n = 2Copy the code

Example 2:

Input: head = [1], n = 1 output: []Copy the code

Example 3:

Input: head = [1,2], n = 1Copy the code

Problem solving: First to traverse the list and retrieve the length of the list, and then according to the linked list node length and n find are trying to remove a node position, is to position the bottom n + 1 node, for n + 1 position from bottom to remove the bottom n position of nodes, so as long as the bottom position of the n + 1 the next node point to the bottom of the location of nodes, n – 1 Change the pointer to delete the node in the reciprocal n position.

 public ListNode removeNthFromEnd(ListNode head, int n) {
        // Get the list length
        int length = 0;
        ListNode lenNode = new ListNode(0, head);
        while(lenNode.next ! =null) {
            length++;
            lenNode = lenNode.next;
        }
        // Delete the rhythm of the first node
        if (length - n - 1= = -1) {
            return head.next;
        }
        ListNode copyNode = head;
        // Go all the way to the last node of the node to be deleted
        for (int i = 0; i < length - n - 1; i++) {
            copyNode = copyNode.next;
        }
        // Delete that node to change the next direction
        copyNode.next = copyNode.next.next;
        return head;
    }

Copy the code

Or, without obtaining the length of the list, use two lists to traverse, and delete the NTH position from the penultimate. When traversing two lists, the difference between the current positions of the two lists is N. When one list is traversed to the end, the position of the other list is the NTH position from the penultimate position. To copy a chain table 2, through the original list node, until the traversal n position, and now at the same time traversing the chain table and table 2, until the end of the chain table (without the next node), the chain table 2 just walk to the NTH node from bottom, because the head with a dummy node chain table 2, so the chain table 2, the current position is reciprocal n nodes before a node, By pointing the current next node in list 2 to the next node, the penultimate node is deleted.

public ListNode removeNthFromEnd(ListNode head, int n) { ListNode listNode = new ListNode(0, head); ListNode copyNode = listNode; For (int I = 0; i < n; i++) { head = head.next; While (head!) {// If (head!) {// If (head!) {// If (head!) {// If (head! = null) { head = head.next; copyNode = copyNode.next; } // Delete node copynode.next = copynode.next-next; return listNode.next; }Copy the code