每日一题——leecode206（反转链表）

题意

难度：简单

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

示例 1：

img

点击并拖拽以移动

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

示例 2：

img

点击并拖拽以移动

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

示例 3：

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

思路代码

代码实现（方法一递归）：

视频讲解：我愿意称之为最清晰的讲解（推荐2倍数使用）

img点击并拖拽以移动

img点击并拖拽以移动

1
2
3
4
5
6
7
8
9
def reverseList(self, head: ListNode) -> ListNode:
    if head is None or head.next is None:
        return head
    
    p = self.reverseList(head.next)
    head.next.next = head
    head.next = None

    return p

代码实现（方法二迭代解法）：

视频讲解：https://leetcode-cn.com/problems/reverse-linked-list/solution/shi-pin-jiang-jie-die-dai-he-di-gui-hen-hswxy/)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 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:
        prev, curr = None, head     #prev是previous前一个，curr是current当前
        while curr is not None:
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next
        return prev