Leetcode:删除链表的倒数第N个结点
题目链接:19. 删除链表的倒数第 N 个结点 – 力扣(LeetCode)
普通版本(统计结点 + 头删 + 中间删除)
主旨:对于链表的删除要考虑头删和尾删的结果
/**
* 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* temp = head;
int sz = 1;
if(head->next == nullptr)
{
return nullptr;
}
while(temp != nullptr && temp->next != nullptr)//先获取整个链表结点的个数
{
temp = temp->next;
++sz;
}
ListNode* prev = head;
ListNode* cur = head->next;
if(n == sz)
{
head = prev->next;
prev->next = nullptr;
return head;
}
--sz;//如果不是头删,那么cur指向的应该是正数第二个,而不是第一个
while(cur != nullptr)
{
if(sz == n)
{
prev->next = cur->next;
cur->next = nullptr;
break;
}
cur = cur->next;
prev = prev->next;
--sz;
}
return head;
}
};
时间复杂度:O(L)(链表的长度)
空间复杂度:O(1)
优化版本(双指针法,待补充)
优化版本(栈法,待补充)
~over~