强制按钮-剑指提供24。反转链表
题目
指剑要约24。反转链表
思路1（迭代）
使用指针pre指向前一个节点，初始值为空，然后遍历链表，同时遍历交换指针指向：
首先使用下一个节点到下一个节点。
然后将cur指向pre。
然后将pre指向cur。
最后，将cur指向nextNode可以完成两个节点的反转。
我们遍历整个链表，对所有节点都这样做，然后把整个链表倒过来。
代码
解决方案类{
公共列表节点反转列表(列表节点头){ 0
//当有多个元素时，确保链表是反转的。
if(head==null | | head . next==null){ 0
返回头；
}
//Common pre指针，存储前一个节点，指向null，因为需要保证第一个元素的下一个可以指向null
//反转过程如下：先存储当前节点的nextNode，然后将当前元素的next指向pre，最后将pre指向head，head指向nextNode。
ListNode pre=null
趁着(头！=null){ 0
ListNode nextNode=head.next
head.next=pre
pre=head
head=nextNode
}
//此时，head指向null，pre指向反转的head节点。
返回前置；
}
}
复杂度分析
时间复杂度：\ O(N)\)
空间复杂度：\ O(1)\)
思路2（递归）
递归比迭代稍微复杂一点。
第一步是递归链接列表。如果你遇到列表的末尾，你将结束递归。这时，你得到的末端节点是倒头节点，所以我们在每一层递归将这个节点传递返回.
当递归到达链表末尾时，我们从链表末尾修改指针：将当前节点下一个节点的下一个指针指向当前节点，即cur.next.next=cur，然后将当前节点cur的指针指向null(如果不指向null，反转后的最后一个节点就不会指向null，从而形成循环)。递归的每一层都是这样做的，最后链表可以反转。
注意：
返回值是最后一个节点。
同时，将cur的下一个指向null。
代码
解决方案类{
公共列表节点反转列表(列表节点头){ 0
//只有链表节点数大于1时，才需要反转。
if(head==null | | head . next==null){ 0
返回头；
}
//反转链接列表
返回dfs(负责人)；
}
公共列表节点dfs(列表节点节点){ 0
//遍历到最后一个节点时开始返回。
if(node . next==null){ 0
返回节点；
}
//获取链表的最后一个节点，也是未来反转后的头节点。
list node last=DFS(node . next)；
//修改链表指针的指向。
//将下一个节点的下一个指向当前节点
node . next . next=node；
//将当前节点指向空
//如果不设置为空，最后一个节点不能指向空，导致循环链表的存在。
node.next=null
最后返回；
}
}
复杂度分析
时间复杂度：\ O(N)\)
复杂性：\(O(N)\)，递归所需的堆栈空间。
我走得很慢，但我从不后退！
内容来源网络，如有侵权，联系删除，本文地址：https://www.230890.com/zhan/103400.html