Loading... ## 题目 反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？ ---------- ## 迭代 ### 算法 `1->2->3->4->5` 变成 `5->4->3->2->1` 目的就是指针都反过来指 我们知道，在单链表中遍历，只能往前，不能回头 先解决一个小问题，目前是`1->2->3`，我要让`1<-2` 我们要让`节点2`的next区域指向`1`，但是此时又没有`节点1`的地址 所以，我们可以定义两个变量，一前一后，`pre` 负责记录 待操作节点之前的节点 `cur` 用来记录当前节点 ### 动图演示 ![无图片描述][1] ### 代码 ```Python # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def reverseList(self, head: ListNode) -> ListNode: next_node = None cur = head while cur: # 保存当前节点的下一个节点 temp = cur.next # 当前节点的指针域指向上一个节点 cur.next = pre # 将pre游标移动到现在节点的位置（记录当前节点地址） pre = cur # 移动当前节点到下一位 cur = next_node return pre ``` ## 递归 ### 算法 这个解法，我是看这里 https://leetcode-cn.com/problems/reverse-linked-list/solution/dong-hua-yan-shi-206-fan-zhuan-lian-biao-by-user74/ 我对递归 动态规划 一直都头疼，但是没办法得学呀！ 递归，这个操作过程是自底向上的 这个过程可以看下方的动图 我们需要一直往下(一直调用自身),直到无法再往下的时候——>处理数据——>层层回溯 那么什么时候？让程序知道，哦！该往回走了。 而不是傻傻的一直调用自身。 这就涉及到递归关键点`停止条件`，可以理解成循环停止的条件吧 数据处理完了，是吧，那么还应当主动`return`返回到上一层 终上所述： 1. 终止条件是当前节点或者下一个节点==null 2. 在函数内部，改变节点的指向，也就是 head 的下一个节点指向 head 递归函数那句 关于本题，要使`7——>5`，可以依靠这行代码 ``` head.next.next = head ``` ![无图片描述][2] 就是要让`7节点的指针域`保存`5节点的地址` ### 动图演示 ![无图片描述][3] ### 代码 ```Python # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def reverseList(self, head: ListNode) -> ListNode: if head is None or head.next is None: return head # cur是最后一个节点，也将反转之后链表的第一个节点 cur = self.reverseList(head.next) # 这一步在上面已经详细解释过了 head.next.next = head # head.next=node又是怎么呢？ head.next = None return cur ``` 接着来看`head.next = None` 这一步是什么意思？ 可以在看下图,当我们做完一次反转操作后，`head`的指针域，还是指向原来的 所以，我们应该把这个链给断开 ![无图片描述][4] [1]: http://assets.z2blog.com//2020/03/26/38b8c0326110449.jif [2]: http://assets.z2blog.com/2020/03/26/f12a10326112918.png [3]: http://assets.z2blog.com//2020/03/26/a3a400326110837.jif [4]: http://assets.z2blog.com/2020/03/26/b45b10326114551.png Last modification：March 26th, 2020 at 11:43 pm © 允许规范转载