学做淘宝店的网站,滁州市建设银行网站,免费公司网站建设,东莞网站建设培训反转链表题目描述
给你单链表的头节点 head #xff0c;请你反转链表#xff0c;并返回反转后的链表。
题解1-迭代
假设链表为 1→2→3→∅#xff0c;我们想要把它改成 ∅←1←2←3。
在遍历链表时#xff0c;将当前节点的 next 指针改为指向前一个节点。由于节点没…反转链表题目描述
给你单链表的头节点 head 请你反转链表并返回反转后的链表。
题解1-迭代
假设链表为 1→2→3→∅我们想要把它改成 ∅←1←2←3。
在遍历链表时将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点因此必须事先存储其前一个节点。在更改引用之前还需要存储后一个节点。最后返回新的头引用。
// 函数反转单链表
struct ListNode* reverseList(struct ListNode* head) {// 初始化前驱节点为 NULLstruct ListNode* prev NULL;// 当前节点指向头节点struct ListNode* curr head;// 循环直到当前节点为空到达链表末尾while (curr) {// 临时保存当前节点的下一个节点struct ListNode* next curr-next;// 将当前节点的指针指向前驱节点完成反转curr-next prev;// 更新前驱节点为当前节点prev curr;// 更新当前节点为下一个节点curr next;}// 循环结束时prev 指向原链表的尾节点也就是反转后链表的头节点// 返回 prev即反转后的链表头节点return prev;
}
在上述代码中prev 并不是直接加入节点的。相反prev 是用来指向当前节点的前一个节点的。在链表反转过程中prev 会跟随着 curr 节点向前移动而 curr 则指向当前正在处理的节点。加入节点的顺序是通过将当前节点的 next 指针指向前一个节点来实现的从而改变了链表的连接顺序达到反转链表的效果。
具体来说在代码中的循环中每一次迭代都会执行以下操作
将当前节点 curr 的下一个节点保存到临时变量 next 中。将当前节点 curr 的 next 指针指向前一个节点 prev实现了链表节点的反转。更新 prev 指向 curr将 curr 设为下一轮迭代的前驱节点。将 curr 设为 next准备处理下一个节点。
通过不断迭代链表并在每一步中更新指针的指向实现了链表的反转。这样循环结束时prev 指向的是原链表的尾节点即新的头节点完成了链表的反转。
题解2递归 // 函数反转单链表
struct ListNode* reverseList(struct ListNode* head) {// 如果链表为空或者只有一个节点则直接返回头节点因为反转后结果不变if (head NULL || head-next NULL) {return head;}// 递归调用反转以头节点的下一个节点为头的子链表struct ListNode* newHead reverseList(head-next);// 将当前头节点的下一个节点的下一个节点指向当前头节点实现链表反转head-next-next head;// 将当前头节点的下一个节点指向 NULL防止形成环head-next NULL;// 返回反转后的新头节点return newHead;
}
这段代码实现了一个递归方法来反转单链表。它的思路是先递归地反转以头节点的下一个节点为头的子链表然后将当前头节点的下一个节点的 next 指针指向当前头节点再将当前头节点的 next 指针指向 NULL最后返回反转后的新头节点。
这种递归方法的关键是理解递归的调用过程以及在每一级递归中如何改变链表节点之间的连接关系从而实现链表的反转。
作者力扣官方题解 链接https://leetcode.cn/problems/reverse-linked-list/solutions/551596/fan-zhuan-lian-biao-by-leetcode-solution-d1k2/ 来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
