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?

Leetcode-cn.com/problems/re…

Example 1:

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

Example 2:

Input: head = [1], n = 1 output: []

Example 3:

Input: head = [1,2], n = 1

Tip:

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

Java solution

Ideas:

  • When I was asked a question in the interview, I answered to switch to double-linked list and stack processing, but I didn’t receive any feedback. Try it this time and see what’s wrong with me
  • Stack solution: the head node into the stack, then out of the stack, to the NTH remove, continue to out of the stack; Simple, but not very efficient
  • Double – linked list: Changed data structure, not very reasonable, deprecated
  • Double pointer: two Pointers are traversed in the same cycle. The interval between the front pointer and the back pointer is N, which ensures that when the front pointer moves to the end, the back pointer is exactly at the previous node of the position to be removed. Very efficient, but for some reason it consumes memory and uses a stack less
package sj.shimmer.algorithm;
import java.util.Stack;

/** * Created by SJ on 2021/2/5. */

class D12 {
    public static void main(String[] args) {
        System.out.println(removeNthFromEnd(ListNode.createNode(new int[] {1.2.3.4.5}),2));
        System.out.println(removeNthFromEnd(ListNode.createNode(new int[] {1}),1));
        System.out.println(removeNthFromEnd(ListNode.createNode(new int[] {1.2}),1));

    }
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return head;
        }
        Stack<ListNode> stack = new Stack<>();
        ListNode temp = head;
        stack.push(temp);
        while(temp.next ! =null) {
            stack.push(temp.next);
            temp = temp.next;
        }
        while(! stack.isEmpty()) {if (n==1) {//n is a number, starting at 1
                ListNode listNode = stack.pop();
                if (stack.isEmpty()) {
                    return listNode.next;
                }else {
                    ListNode pop = stack.pop();
                    pop.next = listNode.next;
                    return head;
                }
            }
            stack.pop();
            n--;
        }
        return head;
    }
     public static ListNode removeNthFromEnd2(ListNode head, int n) {
        if (head == null) {
            return head;
        }
        ListNode temp = head;
        ListNode preRemove = null;
        int i = 0;
        while(temp.next ! =null) {
            i++;
            temp = temp.next;// Move the front pointer
            if (i >=n) {// When the wait interval reaches n, the back pointer starts to move
                if (preRemove == null) {
                    preRemove =head;
                }else{ preRemove = preRemove.next; }}}if (preRemove == null) {N exceeds or equals the length of the list
            if (head == null) {
                return null;
            }
            return head.next;
        }else {
            preRemove.next = preRemove.next.next;
        }
        returnhead; }}Copy the code

The official solution

Leetcode-cn.com/problems/re…

  1. Calculate the list length

    We iterate twice, once to calculate the length, and once to remove the node

    • Time complexity: O(L), where L is the length of the list.
    • Space complexity: O(1)

  2. The stack

    Similar to my stack solution

    • Time complexity: O(L)
    • Space complexity: O(L). Mainly the stack overhead.

  3. A traversal

    Two-pointer solution, but the official solution is written more elegantly

    class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = head;
        ListNode second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first.next;
        }
        while(first ! =null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        ListNode ans = dummy.next;
        returnans; }}Copy the code
    • Time complexity: O(L)
    • Space complexity: O(1).