第一反应头插

这个函数是用来反转一个链表的。函数名为”reverseList”，它接受一个指向链表头节点的指针作为参数，并返回反转后的链表的头节点指针。

函数首先进行一个简单的检查，如果链表为空或者只有一个节点，直接返回原链表头节点，因为无需反转。

接下来，函数递归地调用自身，传入链表头节点的下一个节点作为参数。这样，函数会一直递归到链表的最后一个节点，并返回最后一个节点作为反转后的链表的头节点指针。

然后，将当前节点的下一个节点的next指针指向当前节点，实现反转操作。也就是将当前节点的next节点指向当前节点本身，将链表的指向反转。

接着，将当前节点的next指针置为nullptr，断开当前节点与下一个节点之间的连接，防止形成循环。

最后，返回递归得到的最后一个节点作为反转后的链表的头节点指针。

总体来说，这个函数使用递归的方式将链表进行反转，通过修改节点的指针关系实现反转操作。每次递归都将当前节点的下一个节点指向当前节点本身，然后断开当前节点与下一个节点之间的连接，逐步完成整个链表的反转。

哪里错？？为什么会Segmentation Fault ?
class Solution {
public:
ListNode reverseList(ListNode head) {
ListNode p=head;
ListNode q=p->next;
ListNode* r=q->next;
if(head==NULL||head->next==NULL) return head;
while(p!=NULL){
q->next=p;
p=q;
q=r;
r=r->next; //防止断链
}
head->next=NULL;
return p;
}
};

肯能是调试不了，但是提交的话就直接过了

ListNode p=head;
ListNode q=p->next;
ListNode* r=q->next;
如果head为空的话，head->next无法执行，q->next也无法执行

一看到这个就想起了尾插法hhhh

建议大家去看语法基础课这道题的视频
我一直一直没搞懂链表翻转的问题 听了那个终于搞懂了！！！！！！！！！！！！！

语法基础课 这一道题就值回票价

夸张啦

收到，哈哈哈哈

我看了语法基础课，但是我不会写，看了y总做了才会，我真菜!

相当于创建一个新的空链表 遍历原链表的同时向新链表的头部添加节点 顺序自然就倒过来了

这题是不是没有虚拟的头节点，就是首元节点

/
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode next;
* ListNode(int x) : val(x), next(NULL) {}
* };
/
class Solution {
public:
ListNode reverseList(ListNode head) {
auto p=head->next;
auto q=p->next;
while(q){
p->next=q->next;
q->next=head->next;
head->next=q;
q=p->next;
}
return head->next;
}
};
求助，为什么会Segmentation Fault ?

第一个代码的prev最后是首节点，不是头结点，应该加上head->next = p;return head;

/
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode next;
* ListNode(int x) : val(x), next(NULL) {}
* };
/
class Solution {
public:
ListNode reverseList(ListNode head) {
if(head == NULL || head->next == NULL)return head;
ListNode *tail = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return tail;
}
};
为什么RE

参数不是指针了

妙呀

ListNode reverseList(ListNode head) {
ListNode pre=head;
ListNode cur=pre->next;
pre->next=NULL;
while(cur){
ListNode* tmp=cur->next;
cur->next=pre;
pre=cur;
cur=tmp;
}
return pre;

}

为什么提示Line 13: Char 32: runtime error: member access within null pointer of type ‘ListNode’ (solution.cpp)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:23:32

第一行没有特判吧，如果序列长度为0，你的代码就会报错

应该不会吧，他先判断的！head再 || 上！head->next ，如果head==NULL也就是说第一个条件成立那么就不会执行!head->next,而是直接返回1

&&运算也有这样的特点，只要目前的信息可以判断出返回值那就会中断了

嗯嗯 我是回复的“层主”的评论，而不是y总的回答

为什么尾插变头插就会不行，输出结果对，就是交不上去。。。。哪位大佬解惑

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        auto p = head;
        ListNode *L = new ListNode(0);
        while(p)
        {
            auto tmp = p;
            p = p->next;
            tmp->next = L->next;
            L->next = tmp;
        }
        return L->next;
    }
};

最好返回之前把结点L给释放了

y总， 我总是在有些题上弄不清递归的最后一步，比如这题的话：并得到原链表的尾节点tail，此时head->next是新链表的尾节点，我们令它的next指针指向head。这句话， 这个递归的最后一个情况应该是 4 ->5-> nullptr, 调用递归函数后是 5- > 4 ->nullptr. 然后针对这个链表的head->next 是尾节点，它的next 指针在这个链表中不是nullptr吗， 怎么还能指向head呢？ 这样类似问题不是很清楚！！！

假设是你所说的情况,此时head指向3，执行reverseList(head->next)后，则有
1->2->3->4->nullptr 和 5->4->nullptr
,执行head->next->next = head;后
1->2->3->4->3->4->3->… 和 5->-4->3->4->3->.... 成了循环
然后执行head->next = nullptr; 后
1->2->3->nullptr 和 5->-4->3->nullptr
后面那条链才是我们正在构造的，然后返回上一层递归
此时head指向2，有
1->2->3->nullptr 和 5->4->3->nullptr
然后
1->2->3->2->3->… 和 5->4->3->2->3->2->…
然后
1->2->nullptr 和 5->4->3->2->nullptr

我现在清楚些了，当时有点糊。
结合题目的实例更加清除一些。
1 -> 2 -> 3 -> 4 -> 5 ->null
最开始的递归此时的head->next = 2,是直接返回的head 的next节点反转的情况, 后面的返回成功的话，就是下面的结果
1 、 5 -> 4 -> 3 -> 2 ->null (1 ->next = 2)
此时别的节点不动， head = 1 (在原点不动)， head->next (已经反转到新链表尾部， 这时候应该1 还是指向2的)

   所以现在只需要将 head->next(2)->next = head(1)  将1 放在2的后面 然后将head(1) ->next = nullptr 即可
   这样就变成 5 -> 4 -> 3 -> 2 -> 1 ->null  了。

迭代方法里，在while循环里开了个变量next，那空间复杂度不应该是O(n)吗？

其实是O(1)

每次迭代完变量会被自动销毁，所以同时只会存在一个变量，不会同时存在n个变量，那么需要的额外空间就是 $O(1)$ 的。

为什么要学递归呢 我始终不理解 所有的递归问题都可以迭代处理 而且迭代的时空复杂度大概率是要更低的。。。

机器本身不需要递归，主要为了方便人类思考。就好比如果我们直接写汇编，可以针对每个问题单独写，效率一定比通用性的C++高多了，但是却不适合人工操作

head->next = nullptr;递归解法里这一行很容易忘记。。。

是的hh 比较细节

这个题我第一个想法就是用stack，是不是没救了？

说明对stack的理解很深刻，不错hh

问下大佬，这道题可以定义一个vector，反转后再返回首元素么？

面试题对空间复杂度要求较高，开一个vector会使用额外 $O(n)$ 的空间，不太好。