乐趣区

反转链表Python3

问题提出:反转一个单链表

解决思路:最先想到的是使用栈来存储链表的第一遍遍历的值。再重新遍历链表,遍历的同时弹出栈的元素(弹出的顺序刚好是链表节点值的倒序),为当前节点赋值当前弹出的值。python 可以直接使用 list 结构存储遍历值,读取的时候倒序读取 list 元素,就相当于栈的原理。

代码如下 (~▽~):

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

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        l = []
        temp = head
        while temp!=None:
            l.append(temp.val)
            temp = temp.next
        i = len(l)-1
        temp2 = head
        while i>=0:
            temp2.val = l[i]
            i-=1
            temp2 = temp2.next
        return head

时间与空间消耗:

题目来源:https://leetcode-cn.com/probl…

退出移动版