class Solution {
public:
int solve(ListNode*& head, int n) {
if (!head->next)
return 1;
int ret = solve(head->next, n);
if (ret == n) {
head->next = head->next->next;
}
return ret+1;
}
ListNode* removeNthFromEnd(ListNode* head, int n) {
if (!head)
return NULL;
int ret = solve(head, n);
return (ret==n) ? head->next : head;
}
};
链表
反转链表
迭代的实现非常简单,使用两个指针——
pre
和cur
,pre
的初始值是 NULL,cur
的初始值是链表头,然后一直往前,缓存cur->next
之后将cur->next
指向pre
,然后更新两个指针。退出条件为cur == NULL
递归的方法,有思路,但是就是写不出来,一度开始严重怀疑自己的水平。思路其实非常简单:
但是这里面有一个坑,就是因为递归函数的参数是指针,而且函数体需要修改指针指向的对象的内容,这就涉及到了函数的传参了。一开始我的答案一直都是 NULL,后面才发现,就是函数传参导致的。
在 C++ 里,函数传参有 3 种:
看着挺玄乎的,画个图就清楚了:
而为什么我一开始的答案一直是 NULL 呢?那是因为参数的默认值就是 NULL,而我是直接值传递的,所有的修改都不会作用于真实的变量。修改为指针或者是引用即可。
2022.4.9 更新: 我发现之前递归的写法过于丑陋了,其实可以通过新增一个类成员变量来轻松实现:
这样看的实现的显得简单了很多了,递归参数也少了,速度也上去了。
环形链表
两种题型,是否成环,以及找到第一个环的节点
首先,假设有两个指针,一个快一个慢,假设链表有环,那么他们一定会相遇的。 为什么?
相交链表
删除链表的倒数第N个节点
有了前面的铺垫以后,这道题其实就很简单了,思路跟反转链表是一样的,用递归:
cur->next = cur->next->next
head->next
即可。