Title Description

Give you a linked list, delete the penultimate node of the linked list, and return the head node of the linked list.

Advanced: can you try using one scan?

Example:

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

preface

When operating the linked list, a common technique is to add a dummy node whose next pointer points to the head node of the linked list. In this way, we don't need to make special judgment on the head node.

For example, in this problem, if we want to delete node y, we need to know the precursor node x of node y and point the pointer of x to the successor node of Y. However, since there is no precursor node in the head node, we need to make special judgment when deleting the head node. However, if we add a dummy node, the precursor node of the head node is the dummy node itself. At this time, we only need to consider the general situation.

In particular, in some languages, memory needs to be managed by itself. Therefore, in the actual interview, we need to actively communicate with the interviewer to reach an agreement on the question of "whether we need to release the space corresponding to the deleted node". The following code does not free up space by default.

Method 1: calculate the length of the linked list

Algorithmic thought

An easy way to think of is that we first traverse the linked list from the node to get the length L of the linked list. Then we traverse the linked list from the first node. When we traverse to the L − n+1 node, it is the node we need to delete.

In order to be consistent with n in the title, the number of nodes starts from 1, and the head node is the node numbered 1.

In order to facilitate the deletion operation, we can traverse L − n+1 nodes from the dummy node. When traversing the L − n+1 node, its next node is the node we need to delete, so we only need to modify the pointer once to complete the deletion operation.

JAVA code

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode cur = dummy;
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        ListNode ans = dummy.next;
        return ans;
    }

    public int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            ++length;
            head = head.next;
        }
        return length;
    }
}

Algorithm complexity

    Time complexity: O(L)，among L Is the length of the linked list.
    Space complexity: O(1). 

Method 2: stack

Algorithmic thought

We can also stack all nodes in turn while traversing the linked list. According to the "first in, last out" principle of the stack, we pop up that the nth node of the stack is the node to be deleted, and the current node at the top of the stack is the precursor node of the node to be deleted. In this way, the deletion operation becomes very convenient.

JAVA code

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        stack<ListNode*> stk;
        ListNode* cur = dummy;
        while (cur) {
            stk.push(cur);
            cur = cur->next;
        }
        for (int i = 0; i < n; ++i) {
            stk.pop();
        }
        ListNode* prev = stk.top();
        prev->next = prev->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};

Algorithm complexity

    Time complexity: O(L)，among L Is the length of the linked list.
    Space complexity: O(L)，among L Is the length of the linked list. Mainly for stack overhead.

Method 3: double pointer

Algorithmic thought

JAVA code

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;
        return ans;
    }
}

Algorithm complexity

    Time complexity: O(L)，among L Is the length of the linked list.
    Space complexity: O(1).