class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int k) {
auto dummy = new ListNode(-1);
dummy->next = head;
int n = 0;
for (auto p = dummy; p; p = p->next) n ++;
auto a = dummy;
for (int i = 0; i < n - k - 1; i ++) a = a->next;
a->next = a->next->next;
return dummy->next;
}
};
因为在删的时候,可能会删掉头结点,凡是头结点可能会变的链表,我们都先人为生成一个虚拟头结点 dummmy->next = head
,虚拟头结点一定是不会被删的,虚拟头结点不算在链表节点个数中
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int k) {
auto dummy = new ListNode(-1);
dummy->next = head;
int n = 0;
for (auto p = dummy; p; p = p->next) n ++;
auto p = dummy;
for (int i = 0; i < n - k - 1; i ++) {
p = p->next;
}
// if (p->next->next != NULL) p->next = p->next->next;
// else p->next = NULL;
//也可以不考虑是否是倒数第一个点,就算是倒数第一个点,本身就有 p->next->next == NULL
p->next = p->next->next;
return dummy->next;
}
};
方法2:快慢指针
快慢指针,快指针先走k步,然后快慢指针一起走,直到快指针走到最后,要注意的是可能是要删除第一个节点,直接return dummy -> next
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int k) {
if (!head || !head->next) return NULL;
auto dummy = new ListNode(-1);
dummy->next = head;
auto p = dummy, q = dummy;
for (int i = 0; i < k; i ++) {
p = p->next;
}
if (!p) return dummy->next; //本题不加也可以
while (p->next) {
p = p->next;
q = q->next;
}
q->next = q->next->next;
return dummy->next;
}
};