链表刷题之反转链表

待我称王封你为后i 2023-09-30 21:53 19阅读 0赞

## 3. 反转链表 ##

[206. 反转链表][206.]

给你单链表的头节点 `head` ，请你反转链表，并返回反转后的链表。

**示例 1：**

![img][]

输入：head = [1,2,3,4,5]
    输出：[5,4,3,2,1]

**示例 2：**

![img][img 1]

输入：head = [1,2]
    输出：[2,1]

**示例 3：**

输入：head = []
    输出：[]

**提示：**

*  链表中节点的数目范围是 `[0, 5000]`
 *  `-5000 <= Node.val <= 5000`

题解一：双指针

# Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    class Solution:
        def reverseList(self, head: ListNode) -> ListNode:
            cur = head  # 头结点
            pre = None  # 前一个节点，初始为空
    
            while cur != None:
                tmp = cur.next  # 保存下一个节点
                cur.next = pre  # 反转，下一个节点指向前一个节点
    
                # 更新节点
                pre = cur   # 移动
                cur = tmp   # 移动，相当于 cur = cur.next
    
            return pre		# pre 最终会移动到最后一个节点，因此返回 pre 即可

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LiMqlg2C-1680442657005)(https://tva1.sinaimg.cn/large/008eGmZEly1gnrf1oboupg30gy0c44qp.gif)\]

--------------------

题解二：递归法

class Solution:
        def reverseList(self, head: ListNode) -> ListNode:
            if (head == None or head.next == None): # 递归退出条件
                return head 
    
            cur = self.reverseList(head.next)   # 递归部分
            head.next.next = head
            head.next = None
            return cur

> 参考：[翻转链表][Link 1]

[206.]: https://leetcode.cn/problems/reverse-linked-list/
[img]: https://img-blog.csdnimg.cn/img_convert/a0d46f0bc2de734c8abe3f63f2081fa4.jpeg
[img 1]: https://img-blog.csdnimg.cn/img_convert/25b72a2cbe5d1059a263deb2231c70b3.jpeg
[Link 1]: https://www.programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E7%89%88%E6%9C%AC