《剑指 Offer》专项突破版 - 面试题 21 : 删除倒数第 n 个节点(C++ 实现)

发布时间:2024年01月21日

目录

前言

方法一、遍历链表两次

方法二、遍历链表一次(前后双指针)



前言

题目链接LCR 021. 删除链表的倒数第 N 个结点 - 力扣(LeetCode)

题目

如果给定一个链表,请问如何删除链表中的倒数第 n 个节点?假设链表中节点的总数为 sz,那么 1 <= n <= sz。要求只能遍历链表一次

例如,输入下图 (a) 中的链表,删除倒数第 2 个节点之后的链表如下图 (b) 所示。


方法一、遍历链表两次

如果可以遍历链表两次,那么这个问题就会变得简单一些。在第 1 次遍历链表时,可以得出链表的节点总数 sz。在第 2 次遍历链表时,可以找出链表的第 sz - n 个节点(即倒数第 n + 1 个节点)。然后把倒数第 n + 1 个节点的 next 指针指向倒数第 n - 1 个节点,这样就可以把倒数第 n 个节点从链表中删除

class Solution {
public:
 ? ?ListNode* removeNthFromEnd(ListNode* head, int n) {
 ? ? ? ?int sz = 0;
 ? ? ? ?ListNode* cur = head;
 ? ? ? ?while (cur)
 ? ? ?  {
 ? ? ? ? ? ?++sz;
 ? ? ? ? ? ?cur = cur->next;
 ? ? ?  }
        
 ? ? ? ?ListNode* prev = nullptr;
 ? ? ? ?for (int i = 0; i < sz - n; ++i)
 ? ? ?  {
 ? ? ? ? ? ?if (i == 0)
 ? ? ? ? ? ? ? ?prev = head;
 ? ? ? ? ? ?else
 ? ? ? ? ? ? ? ?prev = prev->next;
 ? ? ?  }
?
 ? ? ? ?ListNode* del;
 ? ? ? ?if (prev == nullptr)
 ? ? ?  {
 ? ? ? ? ? ?del = head;
 ? ? ? ? ? ?head = head->next;
 ? ? ?  }
 ? ? ? ?else
 ? ? ?  {
 ? ? ? ? ? ?del = prev->next;
 ? ? ? ? ? ?prev->next = prev->next->next;
 ? ? ?  }
 ? ? ? ?delete del;
 ? ? ? ?return head;
 ?  }
};

注意:如果 n 等于链表的节点总数 sz,那么被删除的节点为原始链表的头节点


方法二、遍历链表一次(前后双指针)

但题目要求只能遍历链表一次。为了实现只遍历链表一次就能找到倒数第 n + 1 个节点,可以定义两个指针。第 1 个指针 P1 从链表的头节点开始向前走 n 步,第 2 个指针 P2 保持不动;从第 n + 1 步开始指针 P2 也从链表的头节点开始和指针 P1 以相同的速度遍历。由于两个指针的距离始终保持 n,当指针 P1 指向链表的尾节点时指针 P2 正好指向倒数第 n + 1 个节点

下面以在有 6 个节点的链表中找倒数第 3 个节点为例一步步分析这个过程。首先用第 1 个指针 P1 从头节点开始向后走 2 步到达第 3 个节点,如下图 (a) 所示。然后初始化第 2 个指针 P2,让它指向链表的头节点,如下图 (b) 所示。最后让两个指针同时向后遍历,当指针 P1 到达链表的为尾节点时指针 P2 刚好指向倒数第 3 个节点,如下图 (c) 所示。

找出链表中倒数第 3 个节点之后再删除倒数第 2 个节点就比较容易,只需要把倒数第 3 个节点的 next 指针指向倒数第 1 个节点就可以。

class Solution {
public:
 ? ?ListNode* removeNthFromEnd(ListNode* head, int n) {
 ? ? ? ?ListNode* front = head;
 ? ? ? ?for (int i = 0; i < n; ++i)
 ? ? ?  {
 ? ? ? ? ? ?front = front->next;
 ? ? ?  }
?
 ? ? ? ?if (front == nullptr)
 ? ? ?  {
 ? ? ? ? ? ?ListNode* del = head;
 ? ? ? ? ? ?head = head->next;
 ? ? ? ? ? ?return head;
 ? ? ?  }
?
 ? ? ? ?ListNode* back = head;
 ? ? ? ?while (front->next)
 ? ? ?  {
 ? ? ? ? ? ?front = front->next;
 ? ? ? ? ? ?back = back->next;
 ? ? ?  }
 ? ? ? ?ListNode* del = back->next;
 ? ? ? ?back->next = back->next->next;
 ? ? ? ?delete del;
 ? ? ? ?return head;
 ?  }
};
文章来源:https://blog.csdn.net/melonyzzZ/article/details/135733003
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。