Medium

题目描述

给你一个链表，删除链表的倒数第 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+1 步，然后快慢指针同时移动。当快指针到达末尾时，慢指针恰好指向要删除结点的前一个位置。

具体步骤：

  1. 创建一个哨兵结点指向 head，这样可以统一处理删除头结点的情况
  2. 设置 fast 和 slow 两个指针都指向哨兵结点
  3. fast 指针先移动 n+1 步
  4. 然后 fast 和 slow 同时移动，直到 fast 指向 null
  5. 此时 slow 指向要删除结点的前一个结点，执行删除操作

使用哨兵结点的好处是避免了特殊处理删除头结点的情况，代码更加简洁统一。

代码实现

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* fast = dummy;
        ListNode* slow = dummy;
        
        // fast指针先移动n+1步
        for (int i = 0; i <= n; i++) {
            fast = fast->next;
        }
        
        // fast和slow同时移动
        while (fast != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }
        
        // 删除倒数第n个结点
        ListNode* nodeToDelete = slow->next;
        slow->next = slow->next->next;
        delete nodeToDelete;
        
        ListNode* result = dummy->next;
        delete dummy;
        return result;
    }
};

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        fast = slow = dummy
        
        # fast指针先移动n+1步
        for _ in range(n + 1):
            fast = fast.next
        
        # fast和slow同时移动
        while fast:
            fast = fast.next
            slow = slow.next
        
        # 删除倒数第n个结点
        slow.next = slow.next.next
        
        return dummy.next

public class Solution {
    public ListNode RemoveNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode fast = dummy;
        ListNode slow = dummy;
        
        // fast指针先移动n+1步
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }
        
        // fast和slow同时移动
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        
        // 删除倒数第n个结点
        slow.next = slow.next.next;
        
        return dummy.next;
    }
}

var removeNthFromEnd = function(head, n) {
    const dummy = new ListNode(0, head);
    let fast = dummy;
    let slow = dummy;
    
    // fast指针先移动n+1步
    for (let i = 0; i <= n; i++) {
        fast = fast.next;
    }
    
    // fast和slow同时移动
    while (fast !== null) {
        fast = fast.next;
        slow = slow.next;
    }
    
    // 删除倒数第n个结点
    slow.next = slow.next.next;
    
    return dummy.next;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度双指针解法
时间复杂度O(L)，其中 L 是链表长度，只需要一次遍历
空间复杂度O(1)，只使用常数个额外变量

相关题目