反转链表是基础算法题关键在于理解指针操作。以下是适合初学者的详细思路和代码实现方法一迭代法推荐核心思想使用三个指针prev, curr, next逐个节点反转指向。步骤 初始化prev为NULLcurr指向头节点。 遍历链表时先用next暂存curr-next再将curr-next指向prev。 最后移动prev和curr到下一个位置。代码struct ListNode* reverseList(struct ListNode* head) { struct ListNode *prev NULL; //struct ListNode* 代表返回一个【节点的地址】 struct ListNode *curr head; while (curr ! NULL) { //prev移动到最后一个节点时curr为null struct ListNode *next curr-next; // 暂存下一个节点 curr-next prev; // 反转指向 prev curr; // 移动prev curr next; // 移动curr } return prev; // 新头节点 }难点解析:1.普通数组一整块连续的内存像一串连在一起的车厢紧紧挨在一起。链表一节一节独立的节点每一节只记住下一节在哪里。2.节点是一个小包裹包裹里面装两样东西真正的数据数字 val比如 1、2、3一张小纸条存着下一个包裹的地址 next只要拿到第一个包裹头节点就能顺着它里面的 next 纸条找到后面所有包裹。方法二递归法核心思想递归到链表末端从后向前反转指针。步骤 递归终止条件是当前节点为空或下一个节点为空。 在回溯过程中将当前节点的下一节点的next指向自己并断开原指向。代码struct ListNode* reverseList(struct ListNode* head) { if (head NULL || head-next NULL) { //避免head直接为空节点情况 return head; } struct ListNode *newHead reverseList(head-next); head-next-next head; // 反转指向 这两行代码只有在满足if函数后返回上一层的时候才施行 head-next NULL; // 断开原指向 return newHead; }1-2-3-NULL。意思就是head1时head-next不满足NULL到下一层head2时head-next不满足NULL到下一层head3时head-nextNULL输出newHead3因为节点包括数字与下一个数字地址所以输出为3后返回上一层上一层为head2时执行反转3-next2-nextNULL;最后到head1同理2-next1-nextNULL注意事项函数名字叫reverseList它自己就是反转函数。你定义了一个叫reverseList的工具功能是反转链表在工具内部你又调用了这个工具本身这就叫递归。递归先一路钻到最后一个节点全程不做反转 只有走到链表末尾 return 之后才一层一层回头颠倒箭头 newHead 永远是原链表最后一个节点反转后的表头每层都原样往上传递 head-next-next head 就是把下一个节点反过来指向自己 head-next nullptr 切断原来向后的连线避免循环死链表。
