0206. 反转链表

0206. 反转链表 #

  • 标签:链表
  • 难度:简单

题目大意 #

描述:给定一个单链表的头节点 head

要求:将该单链表进行反转。可以迭代或递归地反转链表。

说明

  • 链表中节点的数目范围是 $[0, 5000]$。
  • $-5000 \le Node.val \le 5000$。

示例

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

解释
翻转前    1->2->3->4->5->NULL
反转后    5->4->3->2->1->NULL

解题思路 #

思路 1:迭代 #

  1. 使用两个指针 curpre 进行迭代。pre 指向 cur 前一个节点位置。初始时,pre 指向 Nonecur 指向 head

  2. precur 的前后指针进行交换,指针更替顺序为:

    1. 使用 next 指针保存当前节点 cur 的后一个节点,即 next = cur.next
    2. 断开当前节点 cur 的后一节点链接,将 curnext 指针指向前一节点 pre,即 cur.next = pre
    3. pre 向前移动一步,移动到 cur 位置,即 pre = cur
    4. cur 向前移动一步,移动到之前 next 指针保存的位置,即 cur = next
  3. 继续执行第 2 步中的 1、2、3、4。

  4. 最后等到 cur 遍历到链表末尾,即 cur == None,时,pre 所在位置就是反转后链表的头节点,返回新的头节点 pre

使用迭代法反转链表的示意图如下所示:

思路 1:代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre = None
        cur = head
        while cur != None:
            next = cur.next
            cur.next = pre
            pre = cur
            cur = next
        return pre

思路 1:复杂度分析 #

  • 时间复杂度:$O(n)$。
  • 空间复杂度:$O(1)$。

思路 2:递归 #

具体做法如下:

  1. 首先定义递归函数含义为:将链表反转,并返回反转后的头节点。
  2. 然后从 head.next 的位置开始调用递归函数,即将 head.next 为头节点的链表进行反转,并返回该链表的头节点。
  3. 递归到链表的最后一个节点,将其作为最终的头节点,即为 new_head
  4. 在每次递归函数返回的过程中,改变 headhead.next 的指向关系。也就是将 head.nextnext 指针先指向当前节点 head,即 head.next.next = head
  5. 然后让当前节点 headnext 指针指向 None,从而实现从链表尾部开始的局部反转。
  6. 当递归从末尾开始顺着递归栈的退出,从而将整个链表进行反转。
  7. 最后返回反转后的链表头节点 new_head

使用递归法反转链表的示意图如下所示:

思路 2:代码 #

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

思路 2:复杂度分析 #

  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(n)$。最多需要 $n$ 层栈空间。

参考资料 #

本站总访问量  次  |  您是本站第  位访问者