LeetCode-019- Removes the NTH node from the list

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 first node of the list.

** Advanced: ** Can you try using a scan implementation?

Examples can be found on the LeetCode website.

Source: LeetCode link: leetcode-cn.com/problems/re… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution 1: use stack

We first iterate through the list, putting the value of the node into the temp stack, then iterate through temp, filtering out the NTH node, and reassembling the rest into the list result, which returns result.

Note: The advanced method can use the double pointer method, to be optimized.

import java.util.Stack;

public class Solution {
    /** * method 1: use stack *@param head
     * @param n
     * @return* /
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        Stack<Integer> temp = new Stack<>();
        while(head ! =null) {
            temp.push(head.val);
            head = head.next;
        }
        Stack<Integer> result = new Stack<>();
        int count = 1;
        boolean findN = false;
        while(! temp.isEmpty()) {if (count == n) {
                temp.pop();
                findN = true;
                count++;
                continue;
            }
            result.push(temp.pop());
            count++;
        }
        if(! findN) {return null;
        }
        ListNode resultNode = new ListNode(-1);
        ListNode next = resultNode;
        while(! result.isEmpty()) { next.next =new ListNode(result.pop());
            next = next.next;
        }
        return resultNode.next;
    }

    public static void main(String[] args) {
        ListNode root = new ListNode(1);
        root.next = new ListNode(2);
        root.next.next = new ListNode(3);
        root.next.next.next = new ListNode(4);
        root.next.next.next.next = new ListNode(5);
        root = removeNthFromEnd(root, 2);
        while(root ! =null) {
            System.out.print(root.val + "- >"); root = root.next; }}}class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next; }}Copy the code

Your efforts today are the foreshadowing of luck. Your efforts today are the flowers of tomorrow.