入口

力扣（LeetCode）官網 - 全球極客摯愛的技術成長平臺備戰技術面試？力扣提供海量技術面試資源，幫助你高效提升編程技能，輕松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/

題目描述

給你一個鏈表，刪除鏈表的倒數第 n 個結點，并且返回鏈表的頭結點。

 

示例 1：

輸入：head = [1,2,3,4,5], n = 2
輸出：[1,2,3,5]

示例 2：

輸入：head = [1], n = 1
輸出：[]

示例 3：

輸入：head = [1,2], n = 1
輸出：[1]

 

提示：

• 鏈表中結點的數目為 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

方法一：棧

• 鏈表順序入棧
• 將鏈表后n個節點出棧
• 獲取需要刪除的第n個元素，變更next
• 返回虛擬節點dummy.next即可

圖示

Java實例

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 定義虛擬節點
        ListNode dummy = new ListNode(0, head);
        Deque<ListNode> stack = new LinkedList<ListNode>();
        
        // 防止需要刪除節點為頭節點時的空指針異常，將虛擬節點推入棧中
        stack.push(dummy);
        
        // 將鏈表中的每個節點推入棧中
        while (head != null) {
            stack.push(head);
            head = head.next;
        }
        
        // 彈出棧中的前n個節點，使棧頂元素為倒數第n個節點的前一個節點
        for (int i = 0; i < n; i++) {
            stack.pop();
        }
        
        // 獲取倒數第n個節點的前一個節點
        ListNode pre = stack.peek();
        
        // 將前一個節點的next指針跳過倒數第n個節點，直接指向倒數第n個節點的下一個節點
        pre.next = pre.next.next;
        
        // 返回虛擬節點的下一個節點作為新鏈表的頭節點
        return dummy.next;
    }
}

復雜度分析

• 時間復雜度：O(L)， L 是鏈表的長度。

• 空間復雜度：O(L)， L 是鏈表的長度，主要為棧的開銷。

方法二：雙指針

        使用快慢指針的方式，快指針與慢指針相差n-1，即快指針比慢指針超前了 n 個節點。 兩個指針同時遍歷鏈表，當快指針指向null時，此時慢指針正好指向倒數第n個元素的前一個元素。

Java示例

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 定義虛擬節點
        ListNode dummy = new ListNode(0, head);
        ListNode first = head;
        ListNode second = dummy;

        // 將第一個指針向前移動 n 步
        for (int i = 0; i < n; i++) {
            first = first.next;
        }

        // 同時移動第一個和第二個指針，直到第一個指針為空
        while (first != null) {
            first = first.next;
            second = second.next;
        }

        // 此時第一個指針到達鏈表尾，second 正好指向倒數第 n 個元素的前一個節點

        // 將前一個節點的 next 指針跳過倒數第 n 個節點，直接指向倒數第 n 個節點的下一個節點
        second.next = second.next.next;

        // 返回虛擬節點的下一個節點作為新鏈表的頭節點
        return dummy.next;
    }
}

復雜度分析

• 時間復雜度：O(L)，L 是鏈表的長度。

• 空間復雜度：O(1)。