Leetcode刷题笔记 19. 删除链表的倒数第N个节点-白红宇

Leetcode刷题笔记 19. 删除链表的倒数第N个节点

阅读量：3748 次

发布时间：2019-05-22

本文共 1398 字，大约阅读时间需要 4 分钟。

19. 删除链表的倒数第N个节点

知识点：快慢指针、链表

时间：2020年10月18日

题目链接：

题目

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例1

输入：

给定一个链表: 1->2->3->4->5, 和 n = 2.

输出：

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

解法

快慢指针快的指针比慢的快n个节点

快慢指针一起走快指针到尾节点的时候慢指针到倒数第n个节点了。

注意如果删除的是头节点，返回头节点的next

代码

#include 
   
    #include 
    
     using namespace std;struct ListNode {
      int val;   ListNode *next;   ListNode() : val(0), next(nullptr) {
   }   ListNode(int x) : val(x), next(nullptr) {
   }   ListNode(int x, ListNode *next) : val(x), next(next) {
   }};class Solution {
   public:    ListNode* removeNthFromEnd(ListNode* head, int n) {
           ListNode *fast = head;        ListNode *slow = head;        while(n--)            fast = fast->next;        //特殊判断 如果删除的是头节点 返回头节点的后面        if(fast == nullptr)            return head->next;        while(fast->next!=nullptr){
               fast = fast->next;            slow = slow->next;        }        slow->next = slow->next->next;        return head;    }};void print_node(ListNode* head){
       while(head!=nullptr){
           cout<
     
      val<
      
       next;    }}int main(){
       ListNode node1(5);    ListNode node2(4,&node1);    ListNode node3(3,&node2);    ListNode node4(2,&node3);    ListNode node5(1,&node4);    Solution s;    ListNode* ans = s.removeNthFromEnd(&node5, 1);    print_node(ans);    return 0;}