采用的是链式存储结构，使用一组地址任意的存储单元来存放数据元素。在单链表中，存储的每一条数据都是以节点来表示的，每个节点的构成都是：元素（存储数据的存储单元）+指针（存储下一个节点的地址值），如下图所示：
首节点：单链表的开始节点
尾节点：单链表的终端节点
在线性表中，每个节点都有一个唯一的序号，该序号是从0开始递增。通过序号获取单链表的节点时，我们需要从链表的首节点开始，从前往后开始循环遍历，直到遇到查询序号所对应的节点时为止。
以下图为例，我们需要获得序号为 2 的节点，那么就需要依次遍历获得“节点 1”和“节点 2”，然后才能获得序号为 2 的节点，也就是“节点 3”。
首先根据序号获得需要删除的节点，然后让"删除的节点的前一个节点"指向"删除节点的后一个节点"，这就实现了节点的删除操作。
以下图为例，我们需要删除序号为 2 的节点，那么就让“节点 2”指向“节点 4”即可，这样就删除了序号为 2 的节点，也就是删除了“节点 3”。
根据序号插入节点的操作，我们首先应该根据序号找到插入的节点位置，然后让“插入位置的
上一个节点”指向“新插入的节点”，然后再让“新插入的节点”指向“插入位置的节点”，这样就实现了节点的插入操作。
以下图为例，我们需要在序号为 2 的位置插入元素值“0”，首先先把字符串“0”封装为一
个节点对象，然后就让“节点 2”指向“新节点 0”，最后再让“节点 0”指向“节点 3”，这样就插入了一个新节点。
(1) 存储方式比较
顺序表采用一组地址连续的存储单元依次存放数据元素，通过元素之间的先后顺序来确定元素
之间的位置，可以借助CPU的缓存机制，预读数组中的数据，因此访问效率更高，存储空间的利用率较高。
单链表采用一组地址任意的存储单元来存放数据元素，通过存储下一个节点的地址值来确定节
点之间的位置，对CPU缓存不友好，没办法有效预读，因此访问效率低，存储空间的利用率较低。
(2) 时间性能比较
顺序表查找的时间复杂度为 O(1)，插入和删除需要移动元素，因此时间复杂度为 O(n)。若是需要频繁的执行查找操作，但是很少进行插入和删除操作，那么建议使用顺序表。
单链表查找的时间复杂度为 O(n)，插入和删除无需移动元素，因此时间复杂度为 O(1)。若是需要频繁的执行插入和删除操作，但是很少进行查找操作，那么建议使用链表。
补充：根据序号来插入和删除节点，需要通过序号来找到插入和删除节点的位置，那么整体的
时间复杂度为 O(n)。因此，单链表适合数据量较小时的插入和删除操作，如果存储的数据量较大，那么就建议使用别的数据结构，例如使用二叉树来实现。
(3) 空间性能比较
顺序表需要预先分配一定长度的存储空间，如果事先不知道需要存储元素的个数，分配空间过
大就会造成存储空间的浪费，分配空间过小则需要执行耗时的扩容操作。
单链表不需要固定长度的存储空间，可根据需求来进行临时分配，只要有内存足够就可以分配，在链表中存储元素的个数是没有限制的，无需考虑扩容操作。
/*** @author ：zhz* @date ：Created in 2020/12/22* @version: V1.0* @slogan: 天下风云出我辈，一入代码岁月催* @description: node节点类**/
public class ListNode {int value;//值ListNode next;//下一个指针public ListNode(int value) {this.value = =null;}
}/*** @author ：zhz* @date ：Created in 2020/12/22* @version: V1.0* @slogan: 天下风云出我辈，一入代码岁月催* @description: 单链表实现**/
public class MyLinkedList {private ListNode head;//插入链表的头部 data就是插入的数据public void insertHead(int data){//不管当前是否有数据,只需要把新节点的指针，指向已有的head，再把head指向新节点（栈内存的引用）ListNode newNode=new ListNode(data);=head;head=newNode;}//插入链表的中间 假设定义在第N个插入 O(n)public void insertNth(int data,int position){if (position==0){insertHead(data);//头插入}else {ListNode cur=head;for (int i = 0; i < position; i++) {cur&#;//向后遍历到插入元素的前一个节点}ListNode newNode=new ListNode(data);//创建新节点//插入操作&#;=newNode;}}//删除头结点public void deleteHead(){//O(1)head&#;}//删除链表的中间public void deleteNth(int position) {//O(n)if (position==0){deleteHead();}else{ListNode cur=head;for (int i = 0; i < position; i++) {cur&#;//向后遍历到插入元素的前一个节点}//删除操作&#ext;// 表示的是删除的点，后一个next就是我们要指向的}}//找节点public void find(int data) {//O(n)ListNode cur=head;while (cur!=null){if(cur.value==data){break;}cur&#;}}//打印节点public void print(){ListNode cur=head;while (cur!=null){System.out.print(cur.value+" ");cur&#;}System.out.println();}public static void main(String[] args) {MyLinkedList myList = new MyLinkedList();myList.insertHead(5);myList.insertHead(7);myList.insertHead(10);myList.print(); // 10 -> 7 -> 5
// myList.deleteNth(0);
// myList.print(); // 7 -> 5
// myList.deleteHead();
// myList.print(); // 5
// myList.insertNth(11, 1);
// myList.print(); // 5 -> 11
// myList.deleteNth(1);
// myList.print(); // 5}
}
也叫双向链表，采用的是链式储存处结构。在双链表中，每个节点中都有两个指针，分别指向直接前驱节点（保存前一个节点的地址值）和直接后继节点（保存后一个节点的地址值），如下图所示
双链表的任意一个节点，都可以很方便的访问它的直接前驱节点和直接后驱节点，如下图所示
逻辑上无区别，他们均是完成线性表的内容，主要的区别是结构上的构造有所区别
1、单链表
对于一个节点，有储存数据的 data 和指向下一个节点的 next。也就是说，单链表的遍历操作都得通过前节点—>后节点。
2、 双链表
对于一个节点，有储存数据的 data 和指向下一个节点的 next，还有一个指向前一个节点的 pre。也就是说，双链表不但可以通过前节点—>后节点，还可以通过后节点—>前节点。
/*** @author ：zhz* @date ：Created in 2020/12/22* @version: V1.0* @slogan: 天下风云出我辈，一入代码岁月催* @description: 双链表节点类**/
public class DNode {int value; //值DNode next; //下一个的指针DNode pre; //指向的是前一个指针DNode(int value){this.value = = null;this.pre = null;}
}/*** @author ：zhz* @date ：Created in 2020/12/22* @version: V1.0* @slogan: 天下风云出我辈，一入代码岁月催* @description: 双链表实现**/
public class DoubleLinkList { // 双向链表private DNode head; //头private DNode tail; //尾public DoubleLinkList() {head=null;tail=null;}public void insertHead(int data){//插入头部DNode newNode=new DNode(data);if (head==null){tail=newNode;}else{head.pre==head;}head=newNode;}public void deleteHead(){//删除头部if (head==null){//没有数据return;}==null){//表示只有头节点tail=null;}else{pre=null;}head&#;//把第二个节点置为当前头节点}public void deleteKey(int data){//删除指定的数据DNode current=head;while (current.value!=data){if (==null){System.out.println("无节点");return;}current&#;//向后移一位}if (current==head){//表示删除头节点deleteHead();}else{&#;if (current==tail){//删除尾部tail=current.pre;current.pre=null;}else{pre=current.pre;}}}
}
环形链表依旧采用的是链式存储结构，它的特点就是设置首节点和尾节点相互指向，从而实现
让整个链表形成一个环。常见的环形链表有：
(1) 环形单链表
在单链表中，尾节点的指针指向了首节点，从而整个链表形成一个环，如下图所示：
(2) 环形双链表
在双链表中，尾节点的指针指向了首节点，首节点的指针指向了尾节点，从而整个链表形成一
个环，如下图所示：
/*** @author ：zhz* @date ：Created in 2020/12/22* @version: V1.0* @slogan: 天下风云出我辈，一入代码岁月催* @description: 环形单链表的实现**/
public class CycleSingleLinkedList {/*** 用于保存单链表中的首节点*/private CycleNode headNode;/*** 用于保存单链表中的尾节点*/private CycleNode lastNode;/*** 用于保存单链表中节点的个数*/private int size;/*** 添加元素** @param element 需要添加的数据*/public void add(Object element) {// 1.把需要添加的数据封装成节点对象CycleNode node = new CycleNode(element);// 2.处理单链表为空表的情况if (headNode == null) {// 2.1 把 node 节点设置为单链表的首节点headNode = node;// 2.2 把 node 节点设置为单链表的尾节点lastNode = node;} else {// 3.处理单链表不是空表的情况// 3.1 让 lastNode 指向 node 节点 = node;// 3.2 更新 lastNode 的值lastNode = node;}// 4.设置 lastNode 的 next 值为 = headNode;// 5.更新 size 的值size++;}/*** 根据序号获取元素** @param index 序号* @return 序号所对应节点的数据值*/public Object get(int index) {// 1.如果序号的取值小于 0，则证明是不合法的情况if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("序号不合法，index：" + index);}// 2.根据序号获得对应的节点对象CycleNode node = node(index);// 3.获取并返回 node 节点的数据值return node.data;}/*** 根据序号删除元素** @param index 序号*/public void remove(int index) {// 1.判断序号是否合法，合法取值范围：[0, size - 1]if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("序号不合法，index：" + index);}// 2.处理删除节点在开头的情况if (index == 0) {// 2.1 获得删除节点的后一个节点CycleNode nodeNext = ;// 2.2 设置 headNode 的 next 值为 = null;// 2.3 设置 nextNode 为单链表的首节点headNode = nodeNext;// 2.4 设置 lastNode 的 next 值为 = headNode;} else if (index == size - 1) {// 3.处理删除节点在末尾的情况// 3.1 获得删除节点的前一个节点CycleNode preNode = node(index - 1);// 3.2 设置 preNode 的 next 值为 = null;// 3.3 设置 preNode 为单链表的尾节点lastNode = preNode;// 3.4 设置 lastNode 的 next 值为 = headNode;} else { // 4.处理删除节点在中间的情况// 4.1 获得 index-1 所对应的节点对象CycleNode preNode = node(index - 1);// 4.2 获得 index+1 所对应的节点对象CycleNode nodeNext = ;//或者 CycleNode nodeNext= node(index+1);// 4.3 获得删除节点并设置 next 值为 = null;//促进gc// 4.4 设置 preNode 的 next 值为 = nodeNext;}// 5.更新 size 的值size--;// 6.判断 size 的值是否为 0，如果 size 的值为 0，则设置 headNode 和 lastNode 为nullif (size == 0) {headNode = null;lastNode = null;}}/*** 根据序号插入元素** @param index 序号* @param element 需要插入的数据*/public void add(int index, Object element) {// 1.判断序号是否合法，合法取值范围：[0, size]if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("序号不合法，index：" + index);}// 2.把需要添加的数据封装成节点对象CycleNode curNode = new CycleNode(element);if (index==0){// 3.处理插入节点在开头位置的情况// 3.1 设置 node 的 next 值为 =headNode;// 3.2 设置 node 节点为单链表的首节点headNode= curNode;// 3.3 设置 lastNode 的 next 值为 =headNode;}else if (index==size-1){// 4.处理插入节点在末尾位置的情况// 4.1 设置 lastNode 的 next 值为 =curNode;// 4.2 设置 node 节点为单链表的尾节点lastNode=curNode;// 4.3 设置 lastNode 的 next 值为 =headNode;}else{// 5.处理插入节点在中间位置的情况// 5.1 获得 index-1 所对应的节点对象CycleNode preNode = node(index - 1);// 5.2 获得 index 所对应的节点对象CycleNode cNode = ;// 5.3 设置 preNode 的 next 为 =curNode;// 5.4 设置 node 的 next 为 =cNode;}// 6.更新 size 的值size++;
}/*** 根据序号获得对应的节点对象** @param index 序号* @return 序号对应的节点对象*/private CycleNode node(int index) {// 1.判断环形单链表是否为空表if (headNode == null) {throw new NullPointerException("环形单链表为空表");}// 2.定义一个零时节点，用于辅助单链表的遍历操作CycleNode tempNode = headNode;// 3.定义一个循环，用于获取 index 对应的节点对象for (int i = 0; i < index % size; i++) {// 4.更新 tempNode 的值tempNode = ;}// 5.返回 index 对应的节点对象return tempNode;}
}
//实现一：利用LinkedHashMap
import sun.misc.LRUCache;import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Map;/*** @author zhz* @date 2020/06/03* 运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。** 获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。* 写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。* 当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。**/
public class _146_LRU缓存机制 extends LinkedHashMap<Integer, Integer> {private int capacity;/*** 移除最近最少被访问条件之一，通过覆盖此方法可实现不同策略的缓存* LinkedHashMap是默认返回false的，我们可以继承LinkedHashMap然后复写该方法即可* 例如 LeetCode 第 146 题就是采用该种方法，直接 return size() > capacity;* @param eldest* @return*/@Overrideprotected boolean removeEldestEntry(Map.Entry eldest) {return size()>capacity;}public _146_LRU缓存机制(int capacity) {super(capacity,0.75F,true);this.capacity=capacity;}public int get(int key) {OrDefault(key, -1);}public void put(int key, int value) {super.put(key,value);}public static void main(String[] args) {_146_LRU缓存机制 cache = new _146_LRU缓存机制( 2);cache.put(1, 1);cache.put(2, 2);System.out.(1));cache.put(3, 3); // 该操作会使得关键字 2 作废System.out.(2));cache.put(4, 4); // 该操作会使得关键字 1 作废System.out.(1));System.out.(3));System.out.(4));}
}
//实现方式二，维护一个有序的单链表，而有序就是加入的时间排序
描述：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3，1。
现在问你最后留下的人是谁？
比如N=6，M=5
留下的就是1
1 2 3 4 5 6 => 6 1 2 3 4 => 6 1 2 3 =>1 2 3 => 1 3 => 1
/*** @author ：zhz* @date ：Created in 2020/12/23* @version: V1.0* @slogan: 天下风云出我辈，一入代码岁月催* @description: 环形单链表的约瑟夫问题**/
public class Josephus {public static void main(String[] args) {// 创建一个环形单链表Node lastNode = new Node(10);Node node9 = new Node(9, lastNode);Node node8 = new Node(8, node9);Node node7 = new Node(7, node8);Node node6 = new Node(6, node7);Node node5 = new Node(5, node6);Node node4 = new Node(4, node5);Node node3 = new Node(3, node4);Node node2 = new Node(2, node3);Node headNode = new Node(1, node2); = headNode;// 执行约瑟夫方法josephus(headNode, lastNode, 10, 2, 3);}/*** 约瑟夫问题** @param headNode 环形单链表的首节点* @param lastNode 环形单链表的尾节点* @param size 环形单链表中节点的个数* @param start 从编号为 start 的小孩开始报数* @param count 每次数几下*/private static void josephus(Node headNode, Node lastNode, int size, int start, int count) {// 1.处理不合法的情况// 1.1 处理 headNode 为 null 的情况if (headNode == null) {throw new NullPointerException("headNode 为 null");}// 1.2 处理 start 和 count 不合法的情况if (start > size || count > size) {throw new IllegalArgumentException("参数不合法");}// 2.设置编号为 start 的小孩开始报数，并且使用 headNode 指向该节点for (int i = 0; i < start - 1; i++) {// 把 headNode 和 lastNode 往后移动 start-1 次headNode = ;lastNode = ;}// 3.定义一个循环，用于循环的执行报数操作while (size != 0) { // 如果 size 等于 0，则停止报数// 4.执行报数操作，也就是找到需要出圈的小孩，我们使用 headNode 指向需要出圈的节点// 把 headNode 和 lastNode 往后移动 count-1 次for (int i = 0; i < count - 1; i++) {headNode = ;lastNode = ;}// 5.输出需要出圈小孩的编号，也就是输出 headNode 保存的数据值System.out.println(headNode.data);// 6.实现小孩的出圈操作，也就是把 headNode 从环形单链表中删除// 6.1 获得删除节点的后一个节点Node nextNode = ;// 6.2 设置 lastNode 的 next 值为 = nextNode;// 6.3 设置 headNode 的 next 值为 = null;//促进gc// 7.更新 size 的值size--;// 8.设置 headNode 指向 nextNodeheadNode = nextNode;}}/*** 节点类*/private static class Node {/*** 用于保存节点中的数据值*/private Object data;/*** 用于保存下一个节点的地址值*/private Node next;/*** 专门为 data 做初始化的工作** @param data*/public Node(Object data) {this.data = data;}/*** 专门为 data 和 next 做初始化的工作** @param data* @param next*/public Node(Object data, Node next) {this.data = = next;}}}
/*** @author zhz* @date 2020/04/29* 反转链表**/
public class ReverseList {/***解题思路：递归（从下往上看），假设我们 输入: 1->2->3->4->5->NULL，然后我们从5开始看，*我们创建一个新的临时链表来存储返回的数据new_list，当new_list=5,输出new_list=5,因为head的下*一个的为null了，然后我们继续递归new_list=4,***/public ListNode reverseList(ListNode head) {//递归if(head==null || ==null){return head;}ListNode new_list=);//除了头结点外的其他都反转1->2<-3<-4<-==null;return new_list;}//三指针迭代遍历public ListNode reverseList1(ListNode head) { if(head==null){return head;}ListNode tail=null;ListNode first=head;ListNode second&#;while(first!=null){=tail;//头节点的下一个节点是尾节点tail=first; //尾节点变为头节点first=second;//让原先的第二个节点赋值给头节点if(second!=null){second&#;}}return tail;}/*** 迭代* @param head* @return*/public ListNode reverseLinkedList(ListNode head){ListNode cur = head, pre = null;while(cur != null) {ListNode tmp = ; // 暂存后继节点 = pre; // 修改 next 引用指向pre = cur; // pre 暂存 curcur = tmp; // cur 访问下一节点}return pre;}
}
/*** @author ：zhz* @date ：Created in 2020/12/23* @version: V1.0* @slogan: 天下风云出我辈，一入代码岁月催* @description: 链表的中间节点**/
public class MiddleOfTheLinkedList {//第一种：数组法（时间复杂度O(n),空间复杂度O(n)）public ListNode middleNode(ListNode head) {ListNode[] nodes = new ListNode[100];int index = 0;while (head != null) {nodes[index++] = head;head = ;}return nodes[index / 2];}//快慢指针public ListNode middleNode1(ListNode head) {ListNode first = head;ListNode last = head;while (last != null && != null) {first = ;last = ;}return first;}}
/*** @author ：zhz* @date ：Created in 2020/12/24* @version: V1.0* @slogan: 天下风云出我辈，一入代码岁月催* @description: 在O(1)时间删除单链表节点**/
public class DeleteNode {public ListNode deleteNode(ListNode head, int val) {if(head.value==val){;}ListNode pre=head;ListNode cur&#;while (cur!=null&&cur.value!=val){pre=cur;cur&#;}if (cur!=null){&#;}return head;}
}
package com.hr.剑指offer.work1;/*** @author zhz* @date 2020/06/16**/
public class 面试题22_链表中倒数第k个节点 { /*** 双指针* 初始化： 前指针 former 、后指针 latter ，双指针都指向头节点 head 。* 构建双指针距离： 前指针 former 先向前走 kk 步（结束后，* 双指针 former 和 latter 间相距 kk 步）。* 双指针共同移动： 循环中，双指针 former 和 latter 每轮都向前走一步，* 直至 former 走过链表 尾节点 时跳出（跳出后， latter 与尾节点距离为 k-1，即 latter 指向倒数第 kk 个节点）。* 返回值： 返回 latter 即可。*/public ListNode getKthFromEnd(ListNode head, int k) {ListNode first=head;ListNode last=head;for (int i = 0; i < k; i++) {first&#;}while (first!=null){first&#;last&#;}return last;}
}
package com.hr.剑指offer.work1;/*** @author zhz* @date 2020/06/17* 1、初始化： 伪头节点 dum ，节点 cur 指向 dum 。* 2、循环合并： 当 l1或 l2为空时跳出；* 1、当 l1.val<l2.val 时： cur 的后继节点指定为 l1，并 l1向前走一步；* 2、当 l1.val≥l2.val 时： cur 的后继节点指定为 l2，并 l2向前走一步 ；* 3、节点 cur 向前走一步，即 cur = ur&# 。* 3、合并剩余尾部： 跳出时有两种情况，即 l1为空 或 l2为空。* 1、若 l1 != null ： 将 l1添加至节点 cur 之后；* 2、否则： 将 l2添加至节点 cur 之后。* 4、返回值： 合并链表在伪头节点 dumdum 之后，因此返回 即可。**/
public class 面试题25_合并两个排序的链表 {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode dum=new ListNode(0);ListNode cur=dum;while (l1!=null&&l2!=null){if (l1.val<l2.val){=l1;l1= l1.next;}else{=l2;l2= l2.next;}cur&#;}=l1!=null?l1:l2;;}
}
package com.hr;import java.util.Stack;/*** 从尾到头打印单链表（使用栈来实现）*/
public class Test06 {public static void main(String[] args) {// 1.创建一个单链表Node lastNode = new Node(44);Node node3 = new Node(33, lastNode);Node node2 = new Node(22, node3);Node headNode = new Node(11, node2);// 2.从尾到头打印单链表reversePrint(headNode);}/*** 从尾到头打印单链表*利用栈实现* @param headNode 单链表的首节点*/public static void reversePrint(Node headNode) {// 1.处理 headNode 为 null 的情况if (headNode == null) {throw new NullPointerException("headNode 为 null");}// 2.创建一个栈Stack<Node> stack = new Stack<>();// 3.遍历单链表中的所有节点Node tempNode = headNode;while (tempNode != null) {// 4.把遍历出来的节点添加进入栈中stack.push(tempNode);tempNode = Next();}// 5.遍历栈中的所有节点while (!stack.isEmpty()) {Node node = stack.pop();System.out.Data());}}/*** 从尾到头打印单链表（使用递归来实现）* @param headNode 单链表的首节点*/public static void reversePrint(Node headNode) {// 1.判断 headNode 为 null 的情况if (headNode == null) {return;}// 2.从尾到头打印以 headNode 下一个节点为首节点的链表Next());// 3.打印输出 headNode 中的数据值System.out.Data());}
}
package com.hr;/*** 判断单链表是否有环*/
public class Test08 {public static void main(String[] args) {// 1.创建一个单链表Node lastNode = new Node(55);Node node4 = new Node(44, lastNode);Node node3 = new Node(33, node4);Node node2 = new Node(22, node3);Node headNode = new Node(11, node2);lastNode.setNext(node2);// 2.判断单链表是否有环boolean flag = hasCycle(headNode);System.out.println(flag);}/*** 判断单链表是否有环** @param headNode 单链表的首节点* @return 如果单链表有环，则返回 true，否则返回 fasle*/public static boolean hasCycle(Node headNode) {// 1.处理 headNode 为 null 的情况if (headNode == null) {return false;}// 2.定义一个快指针，每次往后走两步Node fast = headNode;// 3.定义一个慢指针，每次往后走一步Node slow = headNode;// 4.定义一个循环，用于判断单链表是否有环while (fast != null && Next() != null) {// 5.设置快慢指针每次往后移动fast = Next().getNext();slow = Next();// 6.如果 fast 和 slow 指向的是同一个节点，则证明单链表有环if (fast == slow) {return true;}}// 7.执行到此处，证明单链表是无环单链表return false;}
}
package com.hr;/*** 从有环链表中，获得环的长度*/
public class Test09 {public static void main(String[] args) {// 1.创建一个单链表Node lastNode = new Node(66);Node node5 = new Node(55, lastNode);Node node4 = new Node(44, node5);Node node3 = new Node(33, node4);Node node2 = new Node(22, node3);Node headNode = new Node(11, node2);lastNode.setNext(node2);// 2.从有环链表中，获得环的长度int size = getCycleLength(headNode);System.out.println(size);}/*** 从有环链表中，获得环的长度** @param headNode 单链表的首节点* @return 如果单链表有环，则返回环中节点的个数，否则返回 0*/public static int getCycleLength(Node headNode) {// 1.获得快慢指针相交的节点Node meetNode = meetNode(headNode);// 2.处理 meetNode 为 null 的情况if (meetNode == null) {return 0;}// 3.定义一个变量，用于保存环中节点的个数int size = 0;// 4.从 meetNode 节点开始，遍历环中的节点// 4.1 定义一个零时节点，用于辅助单链表的遍历Node tempNode = meetNode;// 4.2 定义一个死循环，用于遍历环中的所有节点while (true) {// 4.3 让 tempNode 指向它的下一个节点tempNode = Next();// 4.4 更新 size 的值size++;// 5.如果 tempNode 和 meetNode 指向的是同一个节点，那么就需要停止遍历操作if (tempNode == meetNode) {break;}}// 6.返回环中节点的个数return size;}/*** 获得快慢指针相交的节点** @param headNode 单链表的首节点* @return 如果单链表有环，则返回快慢指针相交的节点，否则返回 null。*/public static Node meetNode(Node headNode) {// 1.处理 headNode 为 null 的情况if (headNode == null) {return null;}// 2.定义一个快指针，每次往后走两步Node fast = headNode;// 3.定义一个慢指针，每次往后走一步Node slow = headNode;// 4.定义一个循环，用于判断单链表是否有环while (fast != null && Next() != null) {// 5.设置快慢指针每次往后移动fast = Next().getNext();slow = Next();// 6.如果 fast 和 slow 指向的是同一个节点，则证明单链表有环if (fast == slow) {return fast;}}// 7.执行到此处，证明单链表是无环单链表return null;}
}
package com.hr;/*** 单链表中，取出环的起始点*/
public class Test10 {public static void main(String[] args) {// 1.创建一个单链表Node lastNode = new Node(66);Node node5 = new Node(55, lastNode);Node node4 = new Node(44, node5);Node node3 = new Node(33, node4);Node node2 = new Node(22, node3);Node headNode = new Node(11, node2);lastNode.setNext(node2);// 2.单链表中，取出环的起始点Node startNode = getStartNode(headNode);System.out.Data());}/*** 单链表中，取出环的起始点** @param headNode 单链表中的首节点* @return 返回带环单链表中环的起始点*/public static Node getStartNode(Node headNode) {// 1.获得带环单链表中环的长度int length = getCycleLength(headNode);// 2.处理 length 为 0 的情况，也就是处理单链表没有环的情况if (length == 0) {return null;}// 3.定义 first 和 second 指针，并且设置初始值为单链表的首节点Node first = headNode, second = headNode;// 4.让 first 指针往后移动 length 次for (int i = 0; i < length; i++) {first = Next();}// 5.定义一个循环，用于获得带环单链表中环的起始点while (first != second) {// 6.设置 first 和 second 每次往后移动一步first = Next();second = Next();}// 6.返回带环单链表中环的起始点return first;}/*** 从有环链表中，获得环的长度** @param headNode 单链表的首节点* @return 如果单链表有环，则返回环中节点的个数，否则返回 0*/public static int getCycleLength(Node headNode) {// 1.获得快慢指针相交的节点Node meetNode = meetNode(headNode);// 2.处理 meetNode 为 null 的情况if (meetNode == null) {return 0;}// 3.定义一个变量，用于保存环中节点的个数int size = 0;// 4.从 meetNode 节点开始，遍历环中的节点// 4.1 定义一个零时节点，用于辅助单链表的遍历Node tempNode = meetNode;// 4.2 定义一个死循环，用于遍历环中的所有节点while (true) {// 4.3 让 tempNode 指向它的下一个节点tempNode = Next();// 4.4 更新 size 的值size++;// 5.如果 tempNode 和 meetNode 指向的是同一个节点，那么就需要停止遍历操作if (tempNode == meetNode) {break;}}// 6.返回环中节点的个数return size;}/*** 获得快慢指针相交的节点** @param headNode 单链表的首节点* @return 如果单链表有环，则返回快慢指针相交的节点，否则返回 null。*/public static Node meetNode(Node headNode) {// 1.处理 headNode 为 null 的情况if (headNode == null) {return null;}// 2.定义一个快指针，每次往后走两步Node fast = headNode;// 3.定义一个慢指针，每次往后走一步Node slow = headNode;// 4.定义一个循环，用于判断单链表是否有环while (fast != null && Next() != null) {// 5.设置快慢指针每次往后移动fast = Next().getNext();slow = Next();// 6.如果 fast 和 slow 指向的是同一个节点，则证明单链表有环if (fast == slow) {return fast;}}// 7.执行到此处，证明单链表是无环单链表return null;}
}
package com.hr;/*** 获得两个单链表相交的第一个交点*/
public class Test11 {public static void main(String[] args) {// 1.创建两个单链表Node lastNode = new Node(77);Node node6 = new Node(66, lastNode);Node node3 = new Node(33, node6);Node node2 = new Node(22, node3);Node head1 = new Node(11, node2);Node node5 = new Node(55, node6);Node head2 = new Node(44, node5);// 2.获得两个单链表相交的第一个交点Node commonNode = getFirstCommonNode(head1, head2);System.out.Data());}/*** 获得两个单链表相交的第一个交点* 49** @param head1 单链表 1 的首节点* @param head2 单链表 2 的首节点* @return 返回两个单链表相交的第一个交点*/public static Node getFirstCommonNode(Node head1, Node head2) {// 1.处理 head1 或 head2 为 null 的情况if (head1 == null || head2 == null) {return null;}// 2.获得以 head1 为首节点的单链表长度int length1 = getLength(head1);// 3.获得以 head2 为首节点的单链表长度int length2 = getLength(head2);// 4.定义 longNode 指针，用于指向长度较长单链表的首节点Node longNode = length1 > length2 ? head1 : head2;// 5.定义 shortNode 指针，用于指向长度较短单链表的首节点Node shortNode = length1 > length2 ? head2 : head1;// 6.让 longNode 指针往后移动 Math.abs(length1-length2)次for (int i = 0; i < Math.abs(length1 - length2); i++) {longNode = Next();}// 7.定义一个循环，每次让 longNode 和 shortNode 往后移动一次while (longNode != shortNode) {longNode = Next();shortNode = Next();}// 8.返回两个单链表相交的第一个交点return longNode;}/*** 获得单链表的长度** @param headNode 单链表的首节点* @return 返回单链表的长度*/public static int getLength(Node headNode) {// 1.定义一个变量，用于保存单链表的长度int length = 0;// 2.定义一个循环，用于实现单链表的遍历操作Node tempNode = headNode;while (tempNode != null) {tempNode = Next();// 3.更新 length 的值length++;}// 4.返回单链表的长度return length;}
}
package com.hr;/*** 复杂链表的复制*/
public class Test12 {public static void main(String[] args) {// 1.创建一个复杂链表Node lastNode = new Node("E");Node node4 = new Node("D", lastNode);Node node3 = new Node("C", node4);Node node2 = new Node("B", node3);Node headNode = new Node("A", node2);headNode.random = node3;node2.random = lastNode;node4.random = node2;// 2.复杂链表的复制Node cloneNode = cloneNode(headNode);System.out.println();}/*** 复杂链表的复制** @param headNode 复杂链表的首节点* @return 返回复制后复杂链表的首节点*/public static Node cloneNode(Node headNode) {// 1.处理 headNode 为 null 的情况if (headNode == null) {return null;}// 2.复制复杂链表中的每一个节点，并且把复制的节点添加到被复制节点的后面Node curNode = headNode;while (curNode != null) {// 创建一个复制节点（N'）Node node = new Node(curNode.data);// 设置 node 节点的 next 值为 curNode 的后一个节点 = ;// 设置 curNode 的 next 值为 = node;// 更新 curNode 的值curNode = ;}// 3.设置每一个复制节点的 random 指针curNode = headNode;while (curNode != null) {// 获得复制节点（N'）Node node = ;// 处理 curNode 的 random 指针不为 null 的情况if (curNode.random != null) {// 设置 node 的 random 值为 curNode.random 的下一个节点node.random = ;}// 更新 curNode 的值curNode = ;}// 4.把长链表拆分为两个链表// 定义一个节点，用于保存拷贝后复杂链表的首节点Node head = ;curNode = headNode;while (curNode != null) {// 获得复制节点（N'）Node node = ;// 设置 curNode 的 next 值为 = ;// 设置 node 的 next 值为 de.next = == null ? null : ;// 更新 curNode 的值curNode = ;}// 5.返回拷贝后复杂链表的首节点return head;}/*** 节点类*/private static class Node {/*** 用于保存节点中的数据*/private Object data;/*** 用于保存指向下一个节点的地址值*/private Node next;/*** 用于保存指向任意节点的地址值*/private Node random;/*** 专门为 data 做初始化工作** @param data*/public Node(Object data) {53this.data = data;}/*** 专门为 data 和 next 做初始化工作** @param data* @param next*/public Node(Object data, Node next) {this.data = = next;}}
}
我是小白弟弟，一个在互联网行业的小白，立志成为一名架构师
=1
本文发布于:2024-01-31 12:29:57，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/170667539928522.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
