Remove Nth Node From End of List

19. Remove Nth Node From End of List

分析

创建虚拟头节点
- 为了方便处理边界情况（如删除头节点），创建一个虚拟头节点 dummy，其 next 指向链表头部
计算链表长度
- 遍历链表，用变量 len 记录链表的总长度
定位目标节点的前驱节点
- 倒数第 n 个节点的前驱节点是正数第 len - n 个节点
- 从虚拟头节点开始，移动 len - n 步到目标位置
删除目标节点
- 通过修改前驱节点的 next 指针，跳过目标节点

时间复杂度

需要遍历链表两次，计算链表长度和定位目标节点位置，时间复杂度 O(L)， L 是链表长度

空间复杂度

空间复杂度 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution
{
public:
    ListNode* removeNthFromEnd(ListNode* head, int n)
    {
        // 创建虚拟头节点
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;

        // 计算链表长度
        int len = 0;
        for (ListNode* p = dummy; p; p = p->next)
            ++len;

        // 定位到要删除节点的前驱节点
        ListNode* p = dummy;
        for (int i = 0; i < len - n - 1; ++i)
            p = p->next;

        // 删除目标节点
        p->next = p->next->next;

        // 返回结果链表
        return dummy->next;
    }
};