Given a linked list, remove the n-th node from the end of list and return its head.
Example:
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
删除单链表倒数第N个元素
这题 就是弄俩指针left, right
想办法让 left 扮演 倒数第n+1个节点
让right 扮演倒数第一个节点
思路很容易想到， 主要就是有个链表长度为N的情况要单独处理。
步骤
- 让 right 先left 右移 n次
- 处理 如果链表长度为n时的特殊情况（毕竟此时 right 已经跑出界了）， 直接返回head->next
3.同时右移 left ，right 直到 right 等于最后一个节点
4.此时 left就是倒数第n+1个节点 让n+1直接指向倒数第n-1 个节点就好了.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* left = head;
ListNode* right = head;
if (!head->next || ! head){
return NULL;
}
// 右边的 比 左边的 多走 n次
while (n){
right = right->next;
n--;
}
// cornor case
// 链表长度正好为n 直接删去头节点
if (!right){
return head->next;
}
// left--> -(n+1)
// right --> -1
while(right->next){
left = left->next;
right = right->next;
}
//temp --> -(n-1)
// remove -n == -(n+1) -> -(n-1)
ListNode* temp = left->next->next;
left->next = temp;
return head;
}
};
image.png
