当前位置： 首页 > news >正文

Java实现数据结构——不带头单链表

news 来源：原创 2024/7/4 7:31:12

目录

一、前言

二、实现

2.1 类的创建

2.2 方法的实现

2.2.1 打印链表

2.2.2 插入数据

2.2.2.1 头插

2.2.2.2 尾插

2.2.2.3 返回链表节点个数

2.2.2.4 指定位置插入

2.2.3 删除数据 

2.2.3.1 删除指定位置的数据

2.2.3.2 删除指定数据节点 

2.2.3.3 删除所有指定数据的节点

2.2.3.4 删除链表

三、经典题目

3.1  删除链表中等于给定值 val 的所有节点

3.2 反转一个单链表

3.3 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

3.4 输入一个链表，输出该链表中倒数第k个结点。

3.5 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

 3.6 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前

3.7 链表的回文结构

3.8 输入两个链表，找出它们的第一个公共结点

3.9 给定一个链表，判断链表中是否有环

3.10 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL

一、前言

本文不会详细说理论

可观看笔者之前的文章

http://t.csdnimg.cn/ypsEB

二、实现

2.1 类的创建

将链表作为一个自定义类 MySingleList

一个链表是由节点组成

那么节点就可以是自定义类 MySingleList 的内部类 ListNode

public class MySingleList {static class ListNode{}
}

为方便书写 

这里将存放的数据限制为 int 类型

存放下一个节点的地址

节点的类型都是相同的

而 ListNode 是引用数据类型

里面存放的就是地址

为方便实现

将存储数据类型指定为 int

所以 ListNode 这个类可以这么写

static class ListNode{public int val;public ListNode next;}

给出对应的构造方法

 static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val = val;}}

MySingleList 中有一个默认为空的头结点

public class MySingleList {static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head ;//默认有一个为空的头结点
}

目前就实现到这里

后续根本需要进行补充

2.2 方法的实现

2.2.1 打印链表

从头结点开始，直到尾节点打印完成结束

尾节点就是该节点处的 next 为 null 的节点

如果链表为空

则不打印

 public void print() {//打印链表if(this.head == null){//空链表就不打印System.out.println("当前链表为空");}else {ListNode cur = this.head;while (cur != null){System.out.println(cur.val);cur = cur.next;}}}
}

2.2.2 插入数据

2.2.2.1 头插

将插入的节点作为链表的头结点

原头结点是新节点的 next 节点

    public void addFirst(ListNode listNode){//头插if(this.head == null){//空链表就直接让头节点等于这个节点this.head = listNode;}else {//不为空就让插入的节点成为头结点//原头结点成为插入节点的next节点listNode.next = this.head;head = listNode;}}

测试

public static void main(String[] args) {MySingleList mySingleList = new MySingleList();mySingleList.print();MySingleList.ListNode node1 = new MySingleList.ListNode(1);MySingleList.ListNode node2 = new MySingleList.ListNode(2);MySingleList.ListNode node3 = new MySingleList.ListNode(3);MySingleList.ListNode node4 = new MySingleList.ListNode(4);MySingleList.ListNode node5 = new MySingleList.ListNode(5);MySingleList.ListNode node6 = new MySingleList.ListNode(6);mySingleList.addFirst(node1);mySingleList.addFirst(node2);mySingleList.addFirst(node3);mySingleList.addFirst(node4);mySingleList.addFirst(node5);mySingleList.addFirst(node6);mySingleList.print();}

2.2.2.2 尾插

将新节点插入到链表尾部成为新的尾节点

原尾节点的 next 是新的节点的地址

    public void addLast(ListNode listNode){//尾插if(this.head == null){//为空就直接是头节点了head = listNode;}else {ListNode cur = this.head;while (cur.next != null){cur = cur.next;//找尾节点}cur.next = listNode;//尾插}}

测试

    public static void main(String[] args) {MySingleList mySingleList = new MySingleList();MySingleList.ListNode node1 = new MySingleList.ListNode(1);MySingleList.ListNode node2 = new MySingleList.ListNode(2);MySingleList.ListNode node3 = new MySingleList.ListNode(3);MySingleList.ListNode node4 = new MySingleList.ListNode(4);MySingleList.ListNode node5 = new MySingleList.ListNode(5);MySingleList.ListNode node6 = new MySingleList.ListNode(6);mySingleList.addLast(node1);mySingleList.addLast(node2);mySingleList.addLast(node3);mySingleList.addLast(node4);mySingleList.addLast(node5);mySingleList.addLast(node6);mySingleList.print();}

2.2.2.3 返回链表节点个数

与打印链表数据相同

从头节点开始直到尾节点（包含尾节点）计算节点个数

public int getSize(){int count = 0;if(this.head == null){//空链表就返回0return 0;}else {ListNode cur = this.head;while (cur != null){count++;cur = cur.next;}return count;}}
2.2.2.4 指定位置插入

指定一个位置 index 进行插入 

在进行插入前先要检查 index 的合法性

合法区间是[0, mySingleList.size()]

不合法就抛一个异常

public class IndexillegalityException extends RuntimeException{public IndexillegalityException(String message) {super(message);}
}

进行 index 位置的插入时

需要将 index 位置的前一个节点 prev 的 next 存放地址修改为 newnode 的地址

原 prev 的 next 存放地址为 newnode 的 next 所存放地址 

 public void addAny(int index,ListNode listNode)throws IndexillegalityException{//指定位置插入if(index <0 || index > this.getSize()){//检测指定位置的合法性throw new IndexillegalityException("指定位置不合法!");}if(index == 0){//调头插addFirst(listNode);}else if(index == this.getSize()){//调尾插addLast(listNode);}else {//找指定位置前的节点ListNode prev = this.head;int count = 0;while (count != index - 1){count++;prev = prev.next;}listNode.next = prev.next;//原 prev 的 next 存放地址为 newnode 的 next 所存放地址prev.next = listNode;//prev 的 next 存放地址修改为 newnode 的地址}}

测试

  public static void main(String[] args) {MySingleList mySingleList = new MySingleList();MySingleList.ListNode node1 = new MySingleList.ListNode(123);MySingleList.ListNode node2 = new MySingleList.ListNode(2564);MySingleList.ListNode node3 = new MySingleList.ListNode(789);mySingleList.addAny(0,node2);mySingleList.addAny(1,node3);mySingleList.addAny(2,node1);mySingleList.print();MySingleList.ListNode node4 = new MySingleList.ListNode(56464);mySingleList.addAny(2,node4);System.out.println();mySingleList.print();}

2.2.3 删除数据 

2.2.3.1 删除指定位置的数据

进来首先判空

也要判断指定位置 index 的合法性

合法区间为[0,mySingleList.size())

同时要判断链表是不是空链表

也需要找 index 位置前的一个 prev

让 prev 的 next 存放的地址为 index 位置节点的 next 地址

  public void removeAny(int index) {if (index < 0 || index >= this.getSize()) {//检测指定位置的合法性//不用在进行判空throw new IndexillegalityException("指定位置不合法!");}else if (index == 0){//删除首元素ListNode tmp  = this.head.next;this.head = null;this.head = tmp;}else {//找指定位置前的节点ListNode prev = this.head;int count = 0;while (count != index - 1) {count++;prev = prev.next;}ListNode tmp = prev.next.next;prev.next = null;prev.next = tmp;}}

测试

    public static void main(String[] args) {MySingleList mySingleList = new MySingleList();MySingleList.ListNode node1 = new MySingleList.ListNode(123);MySingleList.ListNode node2 = new MySingleList.ListNode(2564);MySingleList.ListNode node3 = new MySingleList.ListNode(789);MySingleList.ListNode node4 = new MySingleList.ListNode(526);MySingleList.ListNode node5 = new MySingleList.ListNode(564);mySingleList.addAny(0,node2);mySingleList.addAny(1,node3);mySingleList.addAny(2,node1);mySingleList.addAny(3,node4);mySingleList.addAny(4,node5);mySingleList.print();System.out.println("===================");mySingleList.removeAny(4);mySingleList.removeAny(0);mySingleList.removeAny(1);mySingleList.print();}

 

    public static void main(String[] args) {MySingleList mySingleList = new MySingleList();MySingleList.ListNode node1 = new MySingleList.ListNode(123);MySingleList.ListNode node2 = new MySingleList.ListNode(2564);MySingleList.ListNode node3 = new MySingleList.ListNode(789);MySingleList.ListNode node4 = new MySingleList.ListNode(526);MySingleList.ListNode node5 = new MySingleList.ListNode(564);mySingleList.addAny(0,node2);mySingleList.addAny(1,node3);mySingleList.addAny(2,node1);mySingleList.addAny(3,node4);mySingleList.addAny(4,node5);mySingleList.print();System.out.println("===================");mySingleList.removeAny(0);mySingleList.removeAny(0);mySingleList.removeAny(0);mySingleList.removeAny(0);mySingleList.removeAny(0);mySingleList.print();}

2.2.3.2 删除指定数据节点 

先判断链表是不是空链表

再找到要删除的节点之前的节点

如果链表中不存在对应节点值就直接返回

如果存在

删除操作的过程基本一致

    public void removeData(int data) {//判空if (this.head == null) {System.out.println("当前链表为空！");} else if (head.val == data) {head = head.next;} else {ListNode prev = this.head;while (prev.next != null && prev.next.val != data) {//找到节点值等于指定数值之前的节点prev = prev.next;}if (prev.next == null) {System.out.println("当前链表中没有您想要删除的数据");return;}ListNode tmp = prev.next.next;prev.next = null;//删除节点值为data的节点prev.next = tmp;//prev 的 next 存放的地址为 节点值为data 的节点的 next 地址}}

测试

    public static void main(String[] args) {MySingleList mySingleList = new MySingleList();MySingleList.ListNode node1 = new MySingleList.ListNode(1);MySingleList.ListNode node2 = new MySingleList.ListNode(2);MySingleList.ListNode node3 = new MySingleList.ListNode(3);MySingleList.ListNode node4 = new MySingleList.ListNode(4);MySingleList.ListNode node5 = new MySingleList.ListNode(5);MySingleList.ListNode node6 = new MySingleList.ListNode(6);mySingleList.addFirst(node1);mySingleList.addFirst(node2);mySingleList.addFirst(node3);mySingleList.addFirst(node4);mySingleList.addFirst(node5);mySingleList.addFirst(node6);mySingleList.removeData(1);mySingleList.print();System.out.println("=======");mySingleList.removeData(2);mySingleList.print();}

2.2.3.3 删除所有指定数据的节点

将链表中所有节点值为 data 的节点全部删除

这里的思路是类似于双指针法

首先保证 head 节点值不是 data 

定义一个 ListNode 类型的 cur

定义一个 ListNode 类型的 del

 cur一开始都是存放是 head

del 为 null

让 cur 先向后移动

如果 cur 的下一节点 val 值不为 data, 让  cur  向后移动

如果 cur 的下一节点 val 值为 data ,  让 del = cur.next , 让 cur.next = del . next 

执行删除操作

重复以上两个步骤直到 cur.next 为 null 

public void removeDataAll(int data) {while (this.head != null && this.head.val == data) {//保证 head 节点值不是 datathis.head = this.head.next;}if (this.head == null) {//判空return;}ListNode cur = this.head;//双指针思想while (cur.next != null) {if (cur.next.val != data) {cur = cur.next;//如果 cur 的下一节点值 val 值不为 data, 让 cur向后移动} else {ListNode del = cur.next;cur.next = del.next;del = null;
//                如果 cur 的下一节点val 值为 data ,让 del = cur.next ,让 cur.next = del.next//                执行删除操作}}}

测试

    public static void main(String[] args) {MySingleList mySingleList = new MySingleList();MySingleList.ListNode node1 = new MySingleList.ListNode(12);MySingleList.ListNode node2 = new MySingleList.ListNode(23);MySingleList.ListNode node3 = new MySingleList.ListNode(12);MySingleList.ListNode node4 = new MySingleList.ListNode(12);MySingleList.ListNode node5 = new MySingleList.ListNode(45);MySingleList.ListNode node6 = new MySingleList.ListNode(23);MySingleList.ListNode node7 = new MySingleList.ListNode(12);mySingleList.addLast(node1);mySingleList.addLast(node2);mySingleList.addLast(node3);mySingleList.addLast(node4);mySingleList.addLast(node5);mySingleList.addLast(node6);mySingleList.addLast(node7);mySingleList.print();System.out.println("======");mySingleList.removeDataAll(12);mySingleList.print();}

2.2.3.4 删除链表

将整个链表变为空链表

可以直接使用 2.2.3.3 的思想

遇到的每一个都删

定义一个 ListNode 类型的 cur

定义一个 ListNode 类型的 del

    public void del() {//销毁链表if (this.head == null) {//判空return;}ListNode cur = this.head;//双指针思想while (cur.next != null) {ListNode del = cur.next;cur.next = del.next;del = null;
//            如果 cur 的下一节点不为null  ,让 del = cur.next ,让 cur.next = del.next}}

这里是没删头结点的

测试

 public static void main(String[] args) {MySingleList mySingleList = new MySingleList();MySingleList.ListNode node1 = new MySingleList.ListNode(12);MySingleList.ListNode node2 = new MySingleList.ListNode(23);MySingleList.ListNode node3 = new MySingleList.ListNode(12);MySingleList.ListNode node4 = new MySingleList.ListNode(12);MySingleList.ListNode node5 = new MySingleList.ListNode(45);MySingleList.ListNode node6 = new MySingleList.ListNode(23);MySingleList.ListNode node7 = new MySingleList.ListNode(12);mySingleList.addLast(node1);mySingleList.addLast(node2);mySingleList.addLast(node3);mySingleList.addLast(node4);mySingleList.addLast(node5);mySingleList.addLast(node6);mySingleList.addLast(node7);mySingleList.print();System.out.println("======");mySingleList.del();mySingleList.print();}

把头结点在删掉

    public void del() {//销毁链表if (this.head == null) {//判空return;}ListNode cur = this.head;//双指针思想while (cur.next != null) {ListNode del = cur.next;cur.next = del.next;del = null;
//            如果 cur 的下一节点不为null  ,让 del = cur.next ,让 cur.next = del.next}this.head = null;//把头结点置空}

三、经典题目

3.1  删除链表中等于给定值 val 的所有节点

题目来源：https://leetcode.cn/problems/remove-linked-list-elements/description/

这个其实已经在上文代码中实现过了

不过这里换一种思想实现

仍然是先判空

再判断链表的头节点值是否为 val

如果是就让头节点向后移动

直到节点值不等于 val 或 链表为空为止

在进行上述操作后如果链表不为空

定义一个 ListNode 类型的 cur

定义一个 ListNode 类型的 prev

prev 中存放的是 head

cur 中存放的是 head.next

如果 cur 的节点值不为 val，那么 cur 和 prev 都向后移动

如果 cur 的节点值为 val，那么  prev 的 next 存放地址为 cur.next , prev 不动,

cur 向后移动 

重复上述过程直到 cur 为 null 为止

最后返回 head 

class Solution {public ListNode removeElements(ListNode head, int val) {while( head != null && head.val == val ){//保证头节点值不为 valhead = head.next;}if(head == null){//判空return head;}ListNode prev = head;//双指针思想ListNode cur = head.next;while(cur != null){if(cur.val != val){cur = cur.next;prev = prev.next;//如果 cur 的节点值不为 val，那么 cur 和 prev 都向后移动}else{cur = cur.next;prev.next = cur;//如果 cur 的节点值为 val，cur 向后移动,prev 不动,那么  prev 的 next 存放地址为 移动后的 cur ,}}return head;}
}

3.2 反转一个单链表

题目来源：https://leetcode.cn/problems/reverse-linked-list/description/

思路一：

创建一个新的链表

将原链表从头节点开始依次头插进这个新链表中

返回这个新链表的头结点

 public ListNode reverseList(ListNode head) {if (head == null || head.next == null) {//判空或者链表只有一个有效节点return head;}ListNode newhead = null;//新链表while (head != null) {ListNode tmp = newhead;newhead = head;//插入的节点成为新的头节点head = head.next;newhead.next = tmp;//原头头节点成为新头节点的 next 节点}return newhead;//返回新的头节点}

思路二：

在原链表上进行反转

多指针思想

定义 ListNode 类型的 prev, cur ,nextone

初始情况下

prev = null

cur = head

nextone = head.next

让 cur.next = prev

让 prev 移动到 cur 

cur 移动到 nextone

nextone 移动到 nextone.next

重复上述过程直到 cur 为 null

返回 prev 

 public ListNode reverseList2(ListNode head) {if (head == null || head.next == null) {//判空或者链表只有一个有效节点return head;}ListNode prev = null;ListNode cur = head;ListNode nextone = head.next;while(cur != null){cur.next = prev;prev = cur;cur = nextone;if(nextone != null){//为空就不移动了nextone = nextone.next;}// 让 cur.next = prev// 让 prev 移动到 cur// cur 移动到 nextone// nextone 移动到 nextone.next}return prev;}

3.3 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

题目来源：https://leetcode.cn/problems/middle-of-the-linked-list/description/

快慢指针思想

定义 ListNode 类型的 fast slow

初始状态下都位于 head 处

fast 每次向后移动两次

slow 每次向后移动一次

当 fast. next 为 null 时

slow 位于中间节点 返回 slow

对于偶数个节点来说

则是 fast 为 null 时

slow 位于中间节点 返回 slow

    public ListNode middleNode(ListNode head) {
//        给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。if(head == null && head.next == null){//判空或者链表只有一个有效节点return head;}//快慢指针ListNode slow = head;ListNode fast = head;while(fast != null && fast.next != null){slow = slow.next;fast = fast.next.next;//当 fast. next 为 null 时,slow 位于中间节点 返回 slow//对于偶数个节点来说,则是 fast 为 null 时,slow 位于中间节点 返回 slow}return slow;}

3.4 输入一个链表，输出该链表中倒数第k个结点。

题目来源：已下架

找倒数第k个节点

从链表尾开始移动

就是移动 k - 1 后的节点

快慢指针

定义 ListNode 类型的 fast slow

初始状态下都位于 head 处

先让 fast 移动 k - 1 个节点

再让 slow 和 fast 一起向后移动

每次移动一个节点

即让 slow 与 fast 之间始终保持 k - 1

直到 fast.next = null（即fast走到尾节点）

此时 slow 就是倒数第 k 个节点

返回 slow

 public ListNode middleNode(ListNode head ,int k){
//        找倒数第k个节点if(head == null || k <= 0){//判空或k <= 0return head;}ListNode slow = head;ListNode fast = head;int count = k - 1;while (count != 0 ){fast = fast.next;if (fast == null){//判断 k 的合法性return null;}count--;}//让 slow 与 fast 之间始终保持 k - 1//fast.next = null（即fast走到尾节点）while (fast != null){fast = fast.next;slow = slow.next;}//此时 slow 就是倒数第 k 个节点return slow;}

3.5 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

题目来源：https://leetcode.cn/problems/merge-two-sorted-lists/description/ 

创建一个新链表

新链表中存在一个虚拟节点(此处使用了带头链表)

两链表都从头节点开始比较

节点值较小的就尾插进新链表中

然后让节点值较小的节点向后移动

重复上述过程直到其中一个链表为空

再将不为空的链表尾插进新链表

返回新链表的头节点

  public ListNode mergeTwoLists(ListNode list1, ListNode list2) {//判空if (list1 == null) {return list2;}if (list2 == null) {return list1;}ListNode newlist = new ListNode(-1);//新链表ListNode tail = newlist;//两链表都从头节点开始比较////节点值较小的就尾插进新链表中//然后让节点值较小的节点向后移动//重复上述过程直到其中一个链表为空while (list1 != null && list2 != null) {if (list1.val <= list2.val) {tail.next = list1;tail = tail.next;list1 = list1.next;//移动} else {tail.next = list2;tail = tail.next;list2 = list2.next;//移动}}//再将不为空的链表尾插进新链表if (list1 != null) {tail.next = list1;}if (list2 != null) {tail.next = list2;}return newlist.next;}

 3.6 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前

https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

移动后是这种

思路

将节点值大于等于 x 的节点放在一个链表 be 中

将节点值小于 x 的节点放在一个链表 af 中

将 af 尾节点的 next 置空

然后将 be 尾插给 af

返回 be 头节点的值

会出现 x 极大 或 x 极小的情况

public ListNode partition(ListNode pHead, int x) {//现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，// 且不能改变原来的数据顺序，返回重新排列后的链表的头指针。if (pHead == null || pHead.next == null) {//判空或链表只有一个节点return pHead;}ListNode be = null;//小于x的节点ListNode af = null;//大于等于x的节点ListNode bee = null;// be 的尾ListNode aff = null;//af 的尾while (pHead != null) {if (pHead.val < x) {if (be == null) {be = pHead;bee = be;} else {bee.next = pHead;bee = bee.next;}} else {if (af == null) {af = pHead;aff = af;} else {aff.next = pHead;aff = aff.next;}}pHead = pHead.next;}if (af == null) {return be;//对应 x 是极大的情况 任意一节点值都小于 x} else if (be == null) {return af;//对应 x 是极小的情况 任意一节点值都大于等于 x} else {aff.next = null;//将 af 的尾节点指向bee.next = af;//将 af 尾插进 bereturn be;}}

3.7 链表的回文结构

题目来源：https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking

对于一个链表来说

找到他的中间节点（快慢指针）

如果是奇数个节点（fast.next == null）就反转 slow 后的节点

然后与 slow 前的节点（不包含 slow ）一一比较判断节点值是否相等

如果是偶数个节点（fast == null） 就反转 slow 及 slow 以后的节点

然后与 slow 前的节点（包含 slow ）一一比较判断节点值是否相等

 public boolean chkPalindrome(ListNode A) {// write code here//判空 或 只有一个节点if(A == null ){return false;}else if(A.next == null){return true;}ListNode slow = A;ListNode fast = A;ListNode tmp = null;while(fast != null && fast.next != null){//找中间节点fast = fast.next.next;tmp = slow;slow = slow.next;}ListNode prev = null;ListNode cur = null;ListNode nextone = null;if(fast == null){//偶数个节点prev = tmp;cur = slow;nextone = cur.next;while(cur != null){cur.next = prev;prev = cur;cur = nextone;if(nextone != null){//反转nextone = nextone.next;}}while(A != slow){if(A.val != prev.val){return false;}else{A = A.next;prev = prev.next;}}return true;}else{//奇数个节点prev = slow;cur = slow.next;nextone = cur.next;while(cur != null){cur.next = prev;prev = cur;cur = nextone;if(nextone != null){//反转nextone = nextone.next;}}//反转之后 prev 为反转的头结点while(A != slow && prev != slow){if(A.val != prev.val){return false;}else{A = A.next;prev = prev.next;}}return true;}}

3.8 输入两个链表，找出它们的第一个公共结点

题目来源：https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

对于 a 链表来说 公共节点是该链表的第三个节点

对于 b 链表来说 公共节点是该链表的第四个节点

而寻找公共节点的最方便的情况是两个链表的长度相当时，寻找到公共节点

那么当长的链表的头结点先移动两链表长度之差的绝对值，再让两链表一起移动

这是在进行判断有无公共节点就很简单了

直接遍历到为空

找到了就返回

找不到就返回 null

  public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if(headA == null || headB == null){//判空return null;}int lenA = 0;int lenB = 0;//链表长度ListNode curA = headA;ListNode curB = headB;while (curA != null){curA = curA.next;lenA++;}while (curB != null){curB = curB.next;lenB++;}int count = 0;if(lenB > lenA){while(count != lenB - lenA){headB = headB.next;//长的链表移动count++;}while (headA != null && headB != null){if(headA == headB){return headA;}else {headA = headA.next;headB = headB.next;}}return null;}else if(lenB < lenA){while(count != lenA - lenB){headA = headA.next;//长的链表移动count++;}while (headA != null && headB != null){if(headA == headB){return headA;}else {headA = headA.next;headB = headB.next;}}return null;}else {//长度相等while (headA != null && headB != null){if(headA == headB){return headA;}else {headA = headA.next;headB = headB.next;}}return null;}}

3.9 给定一个链表，判断链表中是否有环

题目来源：https://leetcode.cn/problems/linked-list-cycle/description/

快慢指针思想

定义 ListNode 类型的 fast slow

就是一个追及问题

fast 每次向后移动两次

slow 每次向后移动一次

移动后若 fast 与 slow 相等则说明存在环

因为是环结构，所以不会走到空

当fast 为 null 或者 fast.next 为 null 时不存在环

public boolean hasCycle(ListNode head) {//给你一个链表的头节点 head ，判断链表中是否有环。if(head == null){//判空return false;}ListNode fast = head;ListNode slow = head;while (fast != null && fast.next!=null){fast = fast.next.next;slow = slow.next;if(fast == slow){return true;}}return false;}

3.10 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL

题目来源：https://leetcode.cn/problems/linked-list-cycle-ii/description/

思路

在 3.9 的解法基础上

由于是 slow 追 fast

fast 在走完一个环之后才会与 slow 相遇

 设

head 到入口点的距离为 X

相遇点到入口点的距离为 Y

整个环长为 L 

slow 走过的路程便是 X + C - Y

fast 走过的路程便是 X +C + (C - Y)

而 fast 的速度又是 slow 的两倍

fast 走过的路程又可以表示为 2 * (X + C - Y)

联立得

X = Y

这就意味着

从相遇点开始走 X（Y）个长度 

让后从头节点开始走 X（Y）个长度

相遇时就是第一个入环节点

  public ListNode detectCycle(ListNode head) {
//        给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。if (head == null) {//判空return head;}ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if (slow == fast) {ListNode cur = head;while (cur != fast) {cur = cur.next;fast = fast.next;}return cur;}}return null;//出循环说明链表走到空，没环}

在代码中就不必计算长度了

只需要知道原理直接写即可

相关文章：

  • 墨烯的Java技术栈-数据结构与算法基础-010
  • STM32_实现双线程控制LED交替闪烁（UCOS）
  • 【C语言】常见的字符串函数
  • 雷池WAF+Modsecurity安装防护及系统加固
  • 【Qwen2部署实战】Qwen2初体验：用Transformers打造智能聊天机器人
  • 【面试题】IPS（入侵防御系统）和IDS（入侵检测系统）的区别
  • 人脸特征68点识别 C++
  • 哪吒汽车，正在等待“太乙真人”的拯救
  • 监听 web 容器内的网络请求
  • vCenter VXR01405C ALARM Certificate is about to expire
  • 【python】scikit-learn安装失败No matching distribution found for scikit-learn
  • 【数据库原理】总结（期末版）
  • 机器学习 C++ 的opencv实现SVM图像二分类的训练 (二)【附源码】
  • 我在高职教STM32——GPIO入门之按键输入（1）
  • .net core 的缓存方案
  • php的引用
  • 〔开发系列〕一次关于小程序开发的深度总结
  • 3.7、@ResponseBody 和 @RestController
  • extjs4学习之配置
  • java正则表式的使用
  • jdbc就是这么简单
  • Netty 框架总结「ChannelHandler 及 EventLoop」
  • Redash本地开发环境搭建
  • Vue实战(四)登录/注册页的实现
  • 利用DataURL技术在网页上显示图片
  • 前端每日实战 2018 年 7 月份项目汇总（共 29 个项目）
  • 使用 @font-face
  • 腾讯视频格式如何转换成mp4 将下载的qlv文件转换成mp4的方法
  • 优化 Vue 项目编译文件大小
  • 原生JS动态加载JS、CSS文件及代码脚本
  • #1015 : KMP算法
  • #if #elif #endif
  • #我与Java虚拟机的故事#连载16：打开Java世界大门的钥匙
  • （2）(2.4) TerraRanger Tower/Tower EVO(360度)
  • （PWM呼吸灯）合泰开发板HT66F2390-----点灯大师
  • （多级缓存）多级缓存
  • （三十五）大数据实战——Superset可视化平台搭建
  • (未解决)jmeter报错之“请在微信客户端打开链接”
  • (转)AS3正则：元子符,元序列,标志,数量表达符
  • .jks文件（JAVA KeyStore）
  • .Net 6.0 处理跨域的方式
  • .net web项目 调用webService
  • .Net调用Java编写的WebServices返回值为Null的解决方法(SoapUI工具测试有返回值)
  • .net后端程序发布到nignx上，通过nginx访问
  • []我的函数库
  • [＜死锁专题＞]
  • [20160902]rm -rf的惨案.txt
  • [20161101]rman备份与数据文件变化7.txt
  • [AutoSar]BSW_Com02 PDU详解
  • [BZOJ 4129]Haruna’s Breakfast（树上带修改莫队）
  • [c#基础]DataTable的Select方法
  • [C/C++]_[初级]_[关于编译时出现有符号-无符号不匹配的警告-sizeof使用注意事项]
  • [CISCN2019 华东南赛区]Web11
  • [ComfyUI进阶教程] animatediff视频提示词书写要点
  • [C语言]一维数组二维数组的大小