思想:快指针先走k次,然后快慢指针一起走,快指针走到结尾,慢指针指向到数第k个元素。
/**
* 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* getKthFromEnd(ListNode* head, int k)
{
// 快慢指针
if(head == nullptr)
{
return head;
}
ListNode *left = head; // 慢指针
ListNode *right = head; // 快指针
// 快指针先移动k次
while(right != nullptr)
{
right = right->next;
k--;
if(k == 0)
{
break;
}
}
// 快慢指针同时移动
while(right != nullptr)
{
left = left->next;
right = right->next;
}
return left;
}
};
删除链表中倒数第k个结点
https://leetcode.cn/problems/SLwz0R/description/
/**
* 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 *left = head;
ListNode *right = head;
while(n)
{
right = right->next;
n--;
}
if(right == nullptr)
{
return head->next;
}
while(right != nullptr && right->next != nullptr)
{
right = right->next;
left = left->next;
}
left->next = left->next->next;
return head;
}
};