1、题目描述
给你一个链表,删除链表的倒数第 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
进阶:你能尝试使用一趟扫描实现吗?
2、分析
(1)毋庸置疑,肯定是要双指针了(p_cur1/p_cur2);
(2)这里重点就是要却确定p_cur1移动多少步后,p_cur2也跟着一起移动;关于这个点{1,2,3,4,5}比划一下就比较清楚了;
(3)另外就是在输入链表前追加一个节点便于返回数据的玩法了,这个应该作为基本操作记住。
ListNode* xxxfunction(ListNode* head){ListNode cur(0, head);ListNode* p_cur = &cur;ListNode* root = &cur;…………return root->next;
}
关于执行过程,其实如下:
(1)左侧node(0)是我们人为添加进去的节点,指向原链表表头head。
(2)cur1/cur2/root 为各指针的初始状态;
(3)在删除倒数第二个节点的情况下cur1和cur2最终状态如虚线cur1/cur2所示;
(4)显然cur2->next = cur2->next->next 即实现对node(4)的删除;
(5)我们最终返回root->next即可。
3、实现代码
#include <iostream>
#include <string>
#include <vector>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* ptr) : val(x), next(ptr) {}
};class Solution{public:ListNode* removeNthFromEnd(ListNode* head, int n){ListNode cur(0, head);ListNode* p_cur1 = &cur;ListNode* p_cur2 = &cur;ListNode* root = &cur;int i = 0;while(p_cur1 != nullptr){p_cur1 = p_cur1->next;i++;//对着{1,2,3,4,5}笔画一下就知道要在cur1移动了n+1下之后cur2在移动是正合适的。//因为,cur2要停留在目标删除节点的前一个节点上才行。if (i > n+1){p_cur2 = p_cur2->next;}}p_cur2->next = p_cur2->next->next;return root->next;}void print_list(ListNode* head){ListNode *cur_ptr = head;while(cur_ptr != nullptr){cout << cur_ptr->val << ",";cur_ptr = cur_ptr->next;}cout << endl;}
};int main()
{Solution s1;ListNode n5(5);ListNode n4(4, &n5);ListNode n3(3, &n4);ListNode n2(2, &n3);ListNode n1(1, &n2);// ListNode n2(2);// ListNode n1(1, &n2);s1.print_list(&n1);ListNode* head = s1.removeNthFromEnd(&n1, 1);s1.print_list(head);}