【简单】Leetcode-206 反转链表

题目描述

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

image.png

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

解法一

迭代法，通过双指针标记前后继节点

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # 迭代方法
        # 定义前继，后继指针
        pre, cur = None, head
        while cur:
            # 完成前后的next变换。Python 语言特性可以省略中间变量
            cur.next, pre, cur = pre, cur, cur.next
        return pre

解法二

递归。将问题拆分成当前节点与剩余的节点，只需要将剩余节点的第一个节点指向当前节点即可

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # 1 -> 2 -> 3 -> 4 -> 5
        #       __________________
        # 1 <- | 2 -> 3 -> 4 -> 5 | 
        #       ------------------
        #            _____________
        # 1 <- 2 <- | 3 -> 4 -> 5 |
        #            -------------

        # 如果输入为空列表，则直接返回
        if not head: return head
        # 如果输入为最后一个节点，则返回当前节点，开始弹栈
        if not head.next: return head
        
        # 递归
        newHead = self.reverseList(head.next)
        
        # 设置第一个节点的next为当前节点
        head.next.next = head
        # 将当前节点的next置空。如果不设置，则对于最后一次弹栈，原链表头结点会指向第二个节点，导致无限循环
        head.next = None
        
        # 返回新链表的头结点
        return newHead