class Solution public ListNode reverseListListNode head ifhead==nullptrhead-next==nullptr return head; ListNode p = reverseListhead-next; head-next-next = head; head-ne
这段代码是用递归的方法实现单链表的翻转。
首先判断链表是否为空或只有一个节点,如果是,则直接返回该链表。
如果链表有两个或以上节点,递归调用翻转函数 reverseList(),将头节点的下一个节点作为参数传入,得到翻转后的子链表的头节点。
然后将头节点的下一个节点的 next 指针指向头节点,实现翻转。
再将头节点的 next 指针置为 nullptr,避免出现环。
最后返回翻转后的子链表的头节点。
下面是详细的执行过程:
假设原链表为 1->2->3->4->5。
-
第一次递归调用 reverseList(2),传入的参数为头节点的下一个节点 2。
-
第二次递归调用 reverseList(3),传入的参数为头节点的下一个节点 3。
-
第三次递归调用 reverseList(4),传入的参数为头节点的下一个节点 4。
-
第四次递归调用 reverseList(5),传入的参数为头节点的下一个节点 5。
-
第四次递归结束,返回翻转后的子链表的头节点 5。
-
第三次递归结束,返回翻转后的子链表的头节点 5,此时链表变为 4->5->3->4->5。
-
第二次递归结束,返回翻转后的子链表的头节点 5,此时链表变为 3->4->5->2->3->4->5。
-
第一次递归结束,返回翻转后的子链表的头节点 5,此时链表变为 2->3->4->5->1->2->3->4->5。
-
整个递归过程结束,返回翻转后的链表的头节点 5
原文地址: https://www.cveoy.top/t/topic/fHmu 著作权归作者所有。请勿转载和采集!