本文主要是介绍算法day08 链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
4.链表_哔哩哔哩_bilibili
一、判断链表为回文
暴力方式：
从链表头开始将链表每一个元素值依次放入数组中，按下标比较值。
从链表尾开始将链表一半元素值放入stack栈中；每次弹栈比较 弹出的值和 链表值。
快慢指针：
假设有这样一个链表【 1 -> 2 -> 3 -> 2-> 1 】 已知条件只有链表head
开始时快指针，慢指针都指向链表头，循环让快指针走两步，慢指针走一步。
跳出循环：当快指针即将越界时，慢指针指向中点；
跳出循环时为标志拿到链表尾节点tail 实现单向链表反转 【1 -> 2 -> 3 <- 2 <- 1 】
看作两个单向链表的值比较。
二、链表的排序：将链表按左中右的顺序 排序为小中大
暴力方式：
链表转换为数组，使用排序算法。
根据链表结构解决：
创建六个额外链表 节点对象 初始值都为null：
头节点 尾节点
小部份 ： sh st
中间部份: eh et
大部分： bh bt
假设有这样一个单链表【4 -> 6 -> 3 -> 5 -> 8 -> 5 ->2 -> 5 -> 6】：
遍历链表 ，指针指向第一个元素4时：
sh =4 st =4
指针指向第二个元素6时: st 4 < 6
bh = 6 bt =6
指针指向第三个元素3时：3 < st 4
st = 3；
sh指向st此时地址 ：也就是 sh - > 第三个3的地址
指针指向第四个元素5时：st 3 < 5 < 6 bh et = null
eh = 5 et= 5
指针指向第五个元素8时：bt 6 < 8
bt =8；
bh指向bt 此时地址 ：也就是 bh- > 第五个元素8的地址
指针指向第六个元素5时： et 5 = 5
et = 5 //et地址改变为第六个元素5的地址
eh指向et 此时地址 ：也就是 et - > 第六个元素5的地址
指针指向第七个元素2时： eh 5 > 2
st = 2
sh - > 第三个3的地址 -> st
......
将小部分 中间部份 大于部份 链接成一个链表
sh -> st -> eh -> et -> bh -> et
但是这还是理想化的状态，还要考虑某个额外节点对象为null的情况，这个时候需要剔除掉这个节点对象。
三、复制整个链表 单链表的随机指针
链表结构：
public class Node{private Node node;private node random;private int value;public Node( int value){this.value = value}
} 
暴力方式
使用HashMap<Node,Node> ：
譬如键为 ① ， 值就 新创建一个node对象 ①﹡
每一个节点都对应了一个新的节点对象。
可以遍历整个链表，通过查询map的key，完成对map值 的设置，也就完成了整个链表的设置。
根据链表结构解决：
将【1 -> 2->3 -> null 】变为【1 ->1* -> 2-> 2* ->3 -> 3* 】
每两个节点间新插入一个新节点对象
再去考虑创建的新节点对象的属性设置
最后再抽出新创建的节点对象
四、两个单链表相交
这篇关于算法day08 链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
