云野 ☁️

24、反转链表

|
|
访问
本文共531字。
展开

[链表] 24. 反转链表 [3.18]

复习重温：[3.24]

题目描述

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

image-20220324132753236

示例 1：

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

链接：https://leetcode-cn.com/problems/reverse-linked-list

思路：

给了头节点，也就是5.next.data—>4

先把next暂存；

方法1、迭代

执行用时：36 ms, 在所有 Python3 提交中击败了**78.80%**的用户

内存消耗：16 MB, 在所有 Python3 提交中击败了**60.12%**的用户

  • 时间复杂度：O*(*n)，其中 n 是链表的长度。需要遍历链表一次。
  • 空间复杂度：O(1)。

思路总结：

注意：注意暂存下一节点；这也算是双指针吧啊哈

image-20220324132927348 
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
        while curr != None:
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next
        return prev

方法2、递归

执行用时：32 ms, 在所有 Python3 提交中击败了92.91%的用户

内存消耗：20.7 MB, 在所有 Python3 提交中击败了10.06%的用户

时间复杂度：O(n)O(n)，其中 nn 是链表的长度。需要对链表的每个节点进行反转操作。

空间复杂度：O(n)O(n)，其中 nn 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 nn 层。

思路总结：链表有天然的递归性。

能递归的条件：1、大问题可拆分成两个子问题；2、子问题求解与大问题一样；3、存在最小子问题（也就是终止条件）

代码：1、递：调用函数；2、归：进行反转操作；3、终止条件。

注意：

1
2
3
4
5
6
7
8
9
10
11
12
13
# 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:
        if head == None or head.next == None:  # 如果链表为空或只有1个节点时，返回head（终止条件）
            return head
        p = self.reverseList(head.next)  # 递：调用函数
        head.next.next = head  # 归：反转操作
        head.next = None
        return p