算法学习笔记 —— 链表

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

反转链表

题目描述

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

解题代码

# -*- 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/