0206：反转链表

2015-07-25 约 267 字预计阅读 1 分钟次阅读

力扣第 206 题

题目

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

分析

递归法很简单，也可以用迭代法：

新建哑节点 dum
tail 维护已反转部分的尾节点，初始指向 head
tail 后面还剩节点时，将该节点去除并插入到哑结点后即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dum=ListNode(next=head)
        tail = head
        while tail and tail.next:
            tmp = tail.next
            tail.next = tmp.next
            tmp.next = dum.next
            dum.next = tmp
        return dum.next

43 ms

目录

0206：反转链表

题目

分析

解答