算法学习笔记 —— 链表

本文最后更新于:2022年7月4日 上午

学而时习,本文记录链表操作相关算法练习笔记。

反转链表

题目描述

输入一个链表,反转链表后,输出新链表的表头。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回ListNode
def ReverseList(self, pHead):
# write code here
last_node = None
current_node = pHead

while current_node is not None:
next_node = current_node.next
current_node.next = last_node
last_node = current_node
current_node = next_node

return last_node

复杂度

时间 空间
O(n) O(1)

解题备注

  • 维护当前节点,顺带考虑前后节点,会比较稳健
  • 设置虚拟前置节点,现场生成后置节点,更加鲁棒,甚至同时囊括了输入为None的情况
  • 需要注意返回前置节点作为新链表头

算法学习笔记 —— 链表
https://www.zywvvd.com/notes/study/algorithm/list/about-list/
作者
Yiwei Zhang
发布于
2020年5月21日
许可协议