删除链表的倒数第N个结点

题目描述

  给定一个链表，删除链表的倒数第n个结点，并且返回链表的头结果。进阶:尝试使用一趟扫描实现

输入输出样例

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

题解

对于这道题目我们需要解决的问题两个:

• 如何获取倒数第n个结点的信息
• 如何删除节点

1. 首先是获取倒数第n个结点的的信息,这个我们可以通过快慢指针来进行一个实现。
   • 快慢节点都开始于前哨节点处
   • 快节点先移动n个距离，之后fast与slow保持n个间距向后移动。
   • 当fast移到tail->next时，即fast为空时，停止移动。
2. 删除节点是通过找到n的上一个节点，并改变其next指向，从而实现删除的目的。
   具体代码如下所示：

   /**
    * Definition for singly-linked list.
    * 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* dummy = new ListNode(-1);
           dummy->next = head;
   
           // 设置快慢指针
           ListNode* slow = dummy;
           ListNode* fast = dummy;
   
           // fast 移到到距离slow size=n的地方
           for (int i = 0; i < n+1; ++i) {
               fast = fast->next;
           }
   
           // 当fast不为空时，进行左右指针的移动
           while (fast) {
               slow = slow->next;
               fast = fast->next;
           }
   
           // 删除倒数第n个节点
           ListNode* delNode = slow->next;
           slow->next = delNode->next;
           delete(delNode);
   
           //返回头节点
           return dummy->next;
       }
   };