type
status
date
slug
summary
tags
category
icon
password
😐
从本部分开始，将不定时对数据结构相关题目做一个从头的梳理和总结

链表

链表由一系列节点（Node）组成，每个节点包含自己的数据以及指向下一个结点的指针，链表的特性使得它在插入和删除数据时有着优秀的效率，比数组要快很多。但访问链表的数据时就并不能像数组那么快，因为这意味着我们必须从头节点开始遍历节点，直到找到需要的数据。

LCR 023. 相交链表

给定两个单链表的头节点headA和headB，请找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回null 。
图示两个链表在节点c1开始相交：
notion image
题目数据保证整个链式结构中不存在环。
注意，函数返回结果后，链表必须保持其原始结构 。

思路

改题可以利用哈希集合法解，即首先将ListA遍历，将每个节点都加入哈希集合中，然后遍历ListB，对遍历到的每个节点，判断该节点是否在哈希集合中，如果是，则可以判断相交。
不过可以寻求一种更优雅的解法，双指针解法。直观地讲，让更长的链表先跑一段时间，等到两个链表当前的node到尾节点的距离相同时，一起跑，若有node相同，则该node为相交节点。

题解

LCR 077. 排序链表

给定链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。 示例

思路

这道题我的思路很简单粗暴，转换为数组→对数组排序→转回ListNode。该思路的时间复杂度及空间复杂度主要由排序算法决定。排序算法后续会出专门的专题进行讲解，这里直接使用sort()函数进行排序。

题解

 

LCR 026. 重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln-1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

思路

该题仍然可以通过转换为线性表的方式通过操作下标达到重排目的。但也可以寻求更优雅的做法：寻找中点→链表逆序→合并链表。

题解1

需要指出的是，这里的线性表vec中，实际上存储的是实例化的ListNode，线性表本身没有next属性，但每个链表节点对象本身有 .next 属性，因此在代码中可以看到vec[i].next的操作。

题解2

 
这里主要通过定义三个新的方法来实现题目要求，middleNode：快慢指针找中点，fast走两步，slow走一步，fast到尾巴，slow到中间。reverseList：反转链表，通过一个头一个尾和一个temp变量实现链表逆序。mergeList：交替合并链表。主函数：将链表从中间分开，后半段逆序后交替插入，实现题设要求。