技术, 算法刷题

链表解题技巧汇总

1. 虚拟头节点

虚拟头结点,也就是 dummy 节点,当需要创造一条新链表的时候,可以使用虚拟头结点简化边界情况的处理。

《leetcode:21. 合并两个有序链表》

对于这道题来说,就是需要生成一个虚拟的头节点,然后不断的比较链表 p1 的节点和链表 p2 的节点,然后将较小的节点放置到新的链表节点中。

2. 快慢指针

《141. 环形链表》

《142. 环形链表 II》

对于链表中是否存在环的问题,经典解法就是用两个指针,一个跑得快,一个跑得慢。如果不含有环,跑得快的那个指针最终会遇到null,说明链表不含环;如果含有环,快指针最终会超慢指针一圈,和慢指针相遇,说明链表含有环。

Related post

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

Copyright©2023 青风的后花园网站 保留所有权利 icpICP证: 苏ICP备2021023449号-1