lc-19-删除链表的倒数第 n 个结点-爱代码爱编程
19 删除链表的倒数第 N 个结点
原题链接:删除链表的倒数第 N 个结点
个人解法
思路:
倒数第k个数可以换一个角度来看,倒数第k个数就是倒数第k个数与最后一个数的相距为k(这里包括边界的两个数)。那么我们可以平移这一段距离到起点位置。
设置两个指针 i 和 j,其中 i 指向链表的头,j 指向距离 i 为 k 距离的元素。那么当 j 遍历到链表尾部的时候,此时就变为了满足 j 为指向链表尾部元素, i 距离 j 为 k(包括边界)。
那么 i 所指向元素即为倒数第 k 个数。删除这个数即可。
注意:这里为了删除 i 所指向的数,维护 i 左和右两个指针 l 和 r。用于删除结点 i。
时间复杂度: O ( n ) O(n) O(n)
代码:
/**
* 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) {
if(head->next == nullptr) return nullptr;
ListNode *H = new ListNode();
H->next = head;
if(n == 1) {
ListNode *p = head;
while(p->next->next) {
p = p->next;
}
p->next = nullptr;
return head;
}
ListNode *i = head, *j = H, *l = H, *r = i->next;
for(int i = 0;i < n;i ++) j = j->next;
while(j->next) {
l = i;
i = r;
r = r->next;
j = j->next;
}
l->next = r;
return H->next;
}
};