Java code implementation: delete the penultimate NTH node linked list

Given a one-way linked list, delete the NTH node from the bottom of the list and return the head node. The number n here is a significant number.

Given linked list: 1->2->3->4->5, and n = 2. After removing the penultimate node: 1->2->3->5.Copy the code

First, iterate over the length of the list, then get the last element to remove, and modify node.next –> Node.next-next.

The code is as follows:

/** * Remove the NTH node from the list, first traverse the length of the list, then get the last element to remove, modify the element's node.next --> node.next-next. * * @param head * @param n * @return*/ public SingleNode removeNthFromEnd1(SingleNode head, int n) { SingleNode dummy = new SingleNode(0, head); Int length = 0; SingleNode first = head;while(first ! = null) { length++; first = first.next; } // Find the node labeled (length-n-1) and make it next to the next node. first = head; int index = 0;while (index < length - n - 1) {
            first = first.next;
            index++;
        }
        first.next = first.next.next;
        return dummy.next;
    }

Copy the code

The test code is as follows:

        SingleLinkedList sll = new SingleLinkedList();
        for (int i = 0; i < 5; i++) {
            sll.addLast(i + 1);
        }
        System.out.println(sll.toString());
        SingleNode node1 = removeNthFromEnd1(sll.getFirst(), 2);
        sll.logFromHead("removeNthFromEnd1", node1);

Copy the code

The command output is as follows: Expected

I/System.out: SingleLinkedList:[1, 2, 3, 4, 5]
I/System.out: removeNthFromEnd1:[1, 2, 3, 5]
Copy the code

Interested students can modify the test cases themselves.

Method 2: Use two Pointers, the two Pointers maintain a fixed spacing n+1, then start traversal. When the front pointer points to null, the next pointer points to the node in front of the node to be removed, and we make its next point to its next. Next.

/** * removes the NTH node from the list, using two Pointers. * * @param head * @param n * @return
     */
    public SingleNode removeNthFromEnd2(SingleNode head, int n) {
        SingleNode dummy = new SingleNode(0, head);
        SingleNode left = dummy;
        SingleNode right = dummy;
        for (int i = 0; i <= n; i++) {
            right = right.next;
        }
        while(right ! = null) { left = left.next; right = right.next; } left.next = left.next.next;return dummy.next;
    }
Copy the code

The test code is as follows:

        SingleLinkedList sll = new SingleLinkedList();
        for (int i = 0; i < 5; i++) {
            sll.addLast(i + 1);
        }
        System.out.println(sll.toString());

        SingleNode node2 = removeNthFromEnd2(sll.getFirst(), 2);
        sll.logFromHead("removeNthFromEnd2", node2);
Copy the code

The following output is displayed: As expected.

    SingleLinkedList:[1, 2, 3, 4, 5]
    removeNthFromEnd2:[1, 2, 3, 5]
Copy the code

See the complete code

Just search for SingleLinkedList in the project.

Github Portal github.com/tinyvampire…

Gitee portal gitee.com/tinytongton…

remove-nth-node-from-end-of-list

2, use Java to achieve one-way linked list, and complete the list inversion.