每日一道算法之--链表反转

链表递归

Word count: 806Reading time: 3 min

 2020/03/02   Share

反转链表

力扣第206题:https://leetcode-cn.com/problems/reverse-linked-list/submissions/

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

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

1.递归解决

1.1 创建新的节点

一开始的时候我的想法是,既然是反转链表,那就可以创建一个新的节点来重新存储,然后直接递归到最后的节点,在不断地回溯中将新节点指向回溯的节点.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    new_node = ListNode(0)
    n = new_node
    def reverseList(self, head: ListNode) -> ListNode:
        if not head:return head
        def foo(head):
            if not head.next: return head
            node = foo(head.next)
            if node:
                self.n.next = ListNode(node.val)
                self.n = self.n.next
            return head
        foo(head)
        self.n.next = ListNode(head.val)
        return self.new_node.next

在测试了几个例子都行的通,我就很兴奋的提交了,结果哦吼,提交时间超时……

1.2 在原链表处理

我就在找原因,有可能是因为创建了新节点,处理时间太长,能不能不用新的节点,直接在原本的链表中去改变指针的指向,当获取到最后的节点时直接处理该节点

逐步递归,知道获取到最后的节点
递归回退的时候,一次改变节点的指针,使该节点的下下个指针指向自己,即node.next.next = node
注意的是,要将该节点的下一个指针删除,一开始我没注意,看了官方题解才知道

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next: return head
        node = self.reverseList(head.next)
        head.next.next = head;
        head.next = None;
        return node

1.3 复杂度分析

时间复杂度：O(n)，假设 n 是列表的长度，要层层递归,那么时间复杂度为 O(n)。

空间复杂度：O(n)，由于使用递归，将会使用隐式栈空间。递归深度可能会达到 nn 层。

2.迭代实现

1.1 用栈实现

因为栈是先进先出的数据结构,所以先用栈存储每一个节点,然后在依次取出操作

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next: return head
        stack = []
        while head:
            stack.append(head)
            head = head.next
        n = stack.pop()
        while stack:
            node = stack.pop()
            node.next.next = node
            node.next = None
        return n

1.1.1 复杂度分析

时间复杂度:假设列表长度为n, 进栈的时间复杂度为O(n),出栈的时间复杂度同样为O(n),所以时间复杂度为2*O(n) = O(n)

空间复杂度为:运用了栈的数据结构,所以空间复杂度为O(n)
可以看到效率还是不错的

2.2 官方的双指针解法

当我们要反转一个链表时,只需要改变每一个节点的前驱和后继指针

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head: return None
        prev = None
        cur = head
        while cur:
            cur.next= prev
            prev = cur
            cur = cur.next
        return prev