目录

0206:反转链表

力扣第 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