算法18:LeetCode_链表相关算法题

news/2024/3/28 19:35:41/文章来源:https://blog.csdn.net/chen_yao_kerr/article/details/129127814

链表无小事,只要是涉及到链表的算法题,边界值的设定尤为重要,而且及其容易出错误。这就要求我们平时多加练习。但是,我们在面试和笔试的过程中往往会碰到链表相关的题目,所以我们在笔试的时候一般都会借助系统提供的工具类进行解答,但是在面试的过程中,面试官往往想听到的答案是和链表直接相关的解答。这就要求我们有2套不同的应答方案。

题目1:给定一个单链表的头节点head,请判断该链表是否为回文结构 

package code03.链表_01;import java.util.Stack;/*** 给定一个单链表的头节点head,请判断该链表是否为回文结构* https://leetcode.cn/problems/palindrome-linked-list/** 1)哈希表方法特别简单(笔试用)* 2)改原链表的方法就需要注意边界了(面试用)*/
public class Palindrome_01 {static class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) { this.val = val; }ListNode(int val, ListNode next) { this.val = val; this.next = next; }}//笔试用, 怎么简单怎么来,安全保险最重要public boolean isPalindrome (ListNode head){//Letcode 默认仅有一个节点的链表也是回文if (head == null /*|| head.next == null*/) {return false;}//后进先出,正好和node是反着的Stack stack = new Stack();ListNode node = head;while (node != null) {stack.push(node);node = node.next;}boolean isPadinDrom = true;while (head != null) {if (head.val != ((ListNode) stack.pop()).val) {isPadinDrom = false;break;}head = head.next;}return isPadinDrom;}//面试用, 对链表进行操作,大体思路对即可,高端大气上档次//这种写法节省了额外空间复杂度 Stackpublic boolean isPalindrome2 (ListNode header){//Letcode 默认仅有一个节点的链表也是回文if (header == null /*|| header.next == null*/) {return false;}ListNode fast = header;ListNode slow = header;while (fast != null && fast.next != null && fast.next.next != null) { // fast.next.next != null 判断特别重要fast = fast.next.next;slow = slow.next;}//奇数,slow正好是中间节点。 偶数,slow是2个中间节点靠后的一个ListNode next = slow.next;slow.next = null;ListNode reverseNode = slow; //前一个逆转的node节点、ListNode node2 = null;//逆转回文后半部分链表节点//假设原有链表是1->2->3->2->1 逆转后得到 1 ->2 -> 3 ->null 和 1 -> 2 ->3 -> null结构//假设原有链表是1->2->3->3->2->1 逆转后得到 1 ->2 -> 3 ->null 和 1 -> 2 ->3 -> 3->null结构while (next != null && reverseNode != null) {node2 = next.next;  //记录下一个节点next.next = reverseNode; //当前节点指向之前被逆转的节点reverseNode = next;      //更新被逆转的节点next = node2;            //当前节点来到下一个节点处}//开始比较//因为我们根据快慢指针进行切割并且第一个3作为中间节点,前一段链表是标准的结构;后一段链表存在以下2种情况//1) 奇数,前后链表相同个数;偶数,厚一点链表多一个值。 因此以第一个链表为参考即可. 参考上一个while的备注ListNode cur = header;boolean isPadinDrom = true;node2 = reverseNode;while (cur!= null) {if (cur.val != reverseNode.val) {isPadinDrom = false;break;}cur = cur.next;reverseNode = reverseNode.next;}/*** 如果我们不在意原有链表是否被破坏,那么以下while可以省略* 如果我们还想要保持原有链表结构不被破坏,此处我们需要修复原有链表* 假设原有链表是1->2->3->2->1 逆转后得到 1 ->2 -> 3 ->null 和 1 -> 2 ->3 -> null结构* 假设原有链表是1->2->3->3->2->1 逆转后得到 1 ->2 -> 3 ->null 和 1 -> 2 ->3 -> 3->null结构* 两个链表的最后一个节点在内存中是相同的,因此仅需要参考后一个链表进行修复即可(此处需要重点理解)*/reverseNode = null;while (node2 != null) {next = node2.next;node2.next = reverseNode;reverseNode = node2;node2 = next;}return isPadinDrom;}public static void printNode (ListNode node) {if (node == null) {System.out.println("链表不存在");}System.out.println("当前链表的值为: " + node.val);//递归的方式逐层打印Node的子节点if(node.next != null) {printNode(node.next);}}public static void main(String[] args) {Palindrome_01 test = new Palindrome_01();ListNode node = new ListNode(1);node.next = new ListNode(2);node.next.next = new ListNode(3);node.next.next.next = new ListNode(2);node.next.next.next.next = new ListNode(1);//node.next.next.next.next.next = new Node(1);boolean isPadinDrom = test.isPalindrome(node);System.out.println(isPadinDrom);boolean isPadinDrom2 = test.isPalindrome2(node);System.out.println("测试原链表是否被修复");printNode(node);System.out.println(isPadinDrom2);ListNode node2 = new ListNode(1);node2.next = new ListNode(2);node2.next.next = new ListNode(3);node2.next.next.next = new ListNode(3);node2.next.next.next.next = new ListNode(2);node2.next.next.next.next.next = new ListNode(1);//node2.next.next.next.next.next.next = new Node(1);boolean isPadinDrom3 = test.isPalindrome(node2);System.out.println(isPadinDrom3);boolean isPadinDrom4 = test.isPalindrome2(node2);System.out.println("测试原链表是否被修复");printNode(node2);System.out.println(isPadinDrom4);}
}

题目2:将单向链表按某值划分成左边小、中间相等、右边大的形式

笔试用:

package code03.链表_01;import java.lang.reflect.Array;
import java.util.ArrayList;/*** 将单向链表按某值划分成左边小、中间相等、右边大的形式* 笔试用,典型的快排*/
public class SmallEqualBig_02 {static class Node {int value;Node next;Node(int value) {this.value = value;}}public static void swap(Node[] nodeArr, int a, int b) {Node tmp = nodeArr[a];nodeArr[a] = nodeArr[b];nodeArr[b] = tmp;}public void partition (Node[] nodes, int left, int right) {//以最后一个值为参考值Node pavoit =  nodes[right];int min = left;int max = right;int cur = left;while (cur < max) {if (nodes[cur].value < pavoit.value) {swap(nodes, min++, cur++);}else if (nodes[cur].value > pavoit.value) {swap(nodes, cur, --max);}else {cur++;}}swap(nodes, cur, right);}public Node sort(Node node){if(node == null || node.next == null) {return node;}int n = 0;Node cur = node;while (cur != null) {cur = cur.next;n++;}Node[] arr = new Node[n];cur = node;for (int i =0; i < arr.length; i++) {arr[i] = cur;cur = cur.next;}partition(arr, 0, n-1);cur = arr[0];node = cur;for (int i =1; i < arr.length; i++) {cur.next = arr[i];cur = cur.next;}cur.next = null;return node;}public static void printNode (Node node) {if (node == null) {System.out.println("链表不存在");}System.out.println("当前链表的值为: " + node.value);//递归的方式逐层打印Node的子节点if(node.next != null) {printNode(node.next);}}public static void main(String[] args) {Node head1 = new Node(7);head1.next = new Node(9);head1.next.next = new Node(1);head1.next.next.next = new Node(8);head1.next.next.next.next = new Node(5);head1.next.next.next.next.next = new Node(2);head1.next.next.next.next.next.next = new Node(5);SmallEqualBig_02 test = new SmallEqualBig_02();System.out.println("排序前的节点");printNode(head1);System.out.println("=================");Node n2 = test.sort(head1);printNode(n2);}
}

面试用:

package code03.链表_01;//将单向链表按某值划分成左边小、中间相等、右边大的形式
public class SmallEqualBig_03 {static class Node {int value;Node next;Node(int value) {this.value = value;}}//笔试用, 不借助任何的新对象,纯粹借住现有的链表结构进行操作public Node sort(Node node, int povit) {Node maxStart = null;Node maxEnd = null;Node minStart = null;Node minEnd = null;Node equalStart = null;Node equalEnd = null;while (node != null) {if(node.value < povit) {if (minStart == null) {minStart = node;minEnd = node;}else {minEnd.next = node;minEnd = node;}}else if(node.value > povit) {if (maxStart == null) {maxStart = node;maxEnd = node;}else {maxEnd.next = node;maxEnd = node;}}else {if (equalStart == null) {equalStart = node;equalEnd = node;}else {equalEnd.next = node;equalEnd = node;}}node = node.next;}if (minEnd != null) {if (equalStart != null) {minEnd.next = equalStart;equalEnd.next = null;}else if (maxStart != null) {minEnd.next = maxStart;maxEnd.next = null;}}if (equalEnd != null){if (maxStart != null) {equalEnd.next = maxStart;maxEnd.next = null;}else{equalEnd.next = null;}}return minStart != null ? minStart : equalStart != null ? equalStart : maxStart;}public static void printNode (Node node) {if (node == null) {System.out.println("链表不存在");}System.out.println("当前链表的值为: " + node.value);//递归的方式逐层打印Node的子节点if(node.next != null) {printNode(node.next);}}public static void main(String[] args) {Node head1 = new Node(7);head1.next = new Node(9);head1.next.next = new Node(1);head1.next.next.next = new Node(8);head1.next.next.next.next = new Node(5);head1.next.next.next.next.next = new Node(2);head1.next.next.next.next.next.next = new Node(5);SmallEqualBig_03 test = new SmallEqualBig_03();System.out.println("排序前的节点");printNode(head1);System.out.println("=================");Node n2 = test.sort(head1, 5);printNode(n2);}}

题目3:

一种特殊的单链表节点类描述如下
class Node {
int value;
Node next;
Node rand;
Node(int val) { value = val; }
}
rand指针是单链表节点结构中新增的指针,rand可能指向链表中的任意一个节点,也可能指向null。
给定一个由Node节点类型组成的无环单链表的头节点 head,请实现一个函数完成这个链表的复制,并返回复制的新链表的头节点。
【要求】
时间复杂度O(N),额外空间复杂度O(1)

package code03.链表_01;import java.util.HashMap;
import java.util.Map;/*** 一种特殊的单链表节点类描述如下* class Node {* int value;* Node next;* Node rand;* Node(int val) { value = val; }* }* rand指针是单链表节点结构中新增的指针,rand可能指向链表中的任意一个节点,也可能指向null。* 给定一个由Node节点类型组成的无环单链表的头节点 head,请实现一个函数完成这个链表的复制,并返回复制的新链表的头节点。* 【要求】* 时间复杂度O(N),额外空间复杂度O(1)** 解题思路:* 1. 借助系统容器,逐个深拷贝每个指针对象,然后将拷贝的指针串成新指针返回 (笔试用)** 2.深拷贝每个指针对象,并且串联进当前的指针当中,然后将当前链表进行切割,生成新链表并返回(面试用)*/
public class DeepCopyNode_04
{static class Node {int value;Node next;Node rand;Node(int val) {value = val;}}//借助系统容器,笔试用(快准稳)public Node deepCopy1 (Node node){//额外空间复杂度O(1), 此处只生成了一个map对象//而深拷贝N个指针,是题目本身就要求的事情,因此可以忽略题目要求的O(N)空间复杂度Map<Node, Node> map = new HashMap<>();if (node == null) {return node;}//深拷贝每个nodeNode cur = node;while (cur != null) {Node n = new Node(cur.value);map.put(cur, n);cur = cur.next;}//构造新链表cur = node;while (cur != null) {map.get(cur).next = map.get(cur.next);map.get(cur).rand = map.get(cur.rand);cur = cur.next;}return (Node) map.get(node);}//纯链表实现,面试用public Node deepCopy2 (Node node){if (node == null) {return node;}Node cur = node;//假设链表为1-2-3  拷贝完以后就是 1-1-2-2-3-3while (cur != null) {//深拷贝Node n = new Node(cur.value);Node next = cur.next;cur.next = n;n.next = next;cur = next;}cur = node;Node copy = cur.next;//rand有可能是后面指向前面,所以不能提前断开,否则找不到copy后后面的指针对象的randwhile (cur != null && cur.next != null) { //cur.next != null等价于copy != null//假设 b 是copy a的节点,那么b的rand节点肯定就在a.rand节点后面copy.rand = cur.rand != null ? cur.rand.next : null;cur = cur.next.next;  //等价于cur = copy.nextcopy = cur != null ? cur.next : null;}//最后分离cur = node;copy = cur.next;Node ans = copy;while (cur != null && cur.next != null) {Node curNext = cur.next.next;Node copyNext = curNext != null ? curNext.next : null;cur.next = curNext;copy.next = copyNext;cur = curNext;copy = copyNext;}return ans;}public static void printNode (Node node) {if (node == null) {System.out.println("链表不存在");}System.out.println("当前链表的值为: " + node.value);System.out.println("当前链表的random值为: " + (node.rand == null ? null : node.rand.value));//递归的方式逐层打印Node的子节点if(node.next != null) {printNode(node.next);}}public static void main(String[] args) {Node head1 = new Node(7);head1.next = new Node(9);head1.next.next = new Node(1);head1.next.next.next = new Node(8);head1.next.next.next.next = new Node(5);head1.next.next.next.next.next = new Node(2);head1.next.next.next.next.next.next = new Node(5);head1.next.next.rand = head1.next.next.next.next;head1.next.next.next.next.next.next.rand = head1;DeepCopyNode_04 test = new DeepCopyNode_04();Node n = test.deepCopy1(head1);printNode(n);System.out.println("==================");Node n2 = test.deepCopy2(head1);printNode(n2);}
}

题目4:给你一个链表的头节点 head ,判断链表中是否有环。如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ,则返回 true 。 否则,返回 false 。

package code03.链表_01;/*** 给你一个链表的头节点 head ,判断链表中是否有环。** 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。* 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。* 注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。** 如果链表中存在环 ,则返回 true 。 否则,返回 false 。* 链接:https://leetcode.cn/problems/linked-list-cycle*/
public class LoopNode_05 {static class ListNode {int value;ListNode next;ListNode(int value) {this.value = value;}}public boolean hasCycle(ListNode node){//需要使用快慢指针if (node == null || node.next == null || node.next.next == null) {return false;}ListNode fast = node.next.next;ListNode slow = node.next;//跳出当前循环//1) fast == slow 循环链表//2) fast.next 或 fast.next.next 为 null 不是循环链表while (fast.next != null && fast.next.next != null) {if (fast == slow) {break;}fast = fast.next.next;slow = slow.next;}//无环链表if (fast.next == null || fast.next.next == null) {return false;}return true;}}

题目5:给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

package code03.链表_01;/*** 给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。** 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。* 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。* 如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。*  https://leetcode.cn/problems/linked-list-cycle-ii*/
public class LoopNode_05_2
{static class ListNode {int value;ListNode next;ListNode(int value) {this.value = value;}}public ListNode detectCycle(ListNode node){//需要使用快慢指针if (node == null || node.next == null || node.next.next == null) {return null;}ListNode fast = node.next.next;ListNode slow = node.next;//跳出当前循环//1) fast == slow 循环链表//2) fast.next 或 fast.next.next 为 null 不是循环链表while (fast.next != null && fast.next.next != null) {if (fast == slow) {break;}fast = fast.next.next;slow = slow.next;}//无环链表if (fast.next == null || fast.next.next == null) {return null;}//有环链表fast = node;//备注1: 找出第一个相交节点,此处根据数据推导公式得出while (fast != slow) {fast = fast.next;slow = slow.next;}//返回fast 或 slow 都对return fast;}public static void main(String[] args) {ListNode head1 = new ListNode(7);ListNode head2 = new ListNode(9); head1.next = head2;ListNode head3 = new ListNode(1); head2.next = head3;ListNode head4 = new ListNode(8); head3.next = head4;ListNode head5 = new ListNode(5); head4.next = head5;ListNode head6 = new ListNode(6); head5.next = head6;ListNode head7 = new ListNode(5); head6.next = head7;LoopNode_05_2 loop = new LoopNode_05_2();//测试无环ListNode loopNode = loop.detectCycle(head1);System.out.println((loopNode != null ? loopNode.value : "null"));//测试有环head7.next = head4; // head4作为环形链表的第一个值ListNode loopNode2 = loop.detectCycle(head1);System.out.println("第一个入环节点的值为: " + (loopNode2 != null ? loopNode2.value : "null"));}
}

此处,需要对代码中的 “备注1” 进行解释一下,为什么fast = node;  while (fast != slow) { fast = fast.next; slow = slow.next;} 当 fast = slow的时候,fast或slow就是相交的第一个节点? 不理解这一点,下面的题目无法继续进行下去

由此图,我们可知: 快指针从A点重新出现,跑了x距离。 那么慢指针就是跑 N圈额外加z一段距离,此时他们正好会在第一个相交的节点相遇。

题目6:给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。题目数据 保证 整个链式结构中不存在环。函数返回结果后,链表必须 保持其原始结构 。

package code03.链表_01;import java.util.HashMap;
import java.util.Map;/*** 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。* 题目数据 保证 整个链式结构中不存在环。函数返回结果后,链表必须 保持其原始结构 。* https://leetcode.cn/problems/intersection-of-two-linked-lists/**/
public class DoubleLoopNodes_06
{static class ListNode {int value;ListNode next;ListNode(int value) {this.value = value;}}//借助java系统提供的容器public ListNode getIntersectionNode(ListNode headA, ListNode headB){if (headA == null || headB == null) {return null;}Map<ListNode, ListNode> map = new HashMap();ListNode cur = headA;while (cur != null) {map.put(cur, cur);cur = cur.next;}cur = headB;while (cur != null) {if (map.containsKey(cur)) {return map.get(cur);}cur = cur.next;}return null;}//纯链表实现public ListNode getIntersectionNode2(ListNode headA, ListNode headB){if (headA == null || headB == null) {return null;}ListNode cur = headA;int n = 0;while (cur != null) {n++;cur = cur.next;}cur = headB;while (cur != null) {n--;cur = cur.next;}ListNode lNode = n > 0 ? headA : headB;   //长链表ListNode sNode = lNode == headA ? headB : headA; //短链表n = Math.abs(n);while (n > 0) {lNode = lNode.next;n--;}//此刻,长链表剩下的节点和短链表剩下的节点个数相同while (lNode != sNode) {lNode = lNode.next;sNode = sNode.next;if(lNode == null || sNode == null) {return null;}}return lNode;}public static void main(String[] args) {//链表1ListNode node1 = new ListNode(4);ListNode node2 = new ListNode(1);//链表2ListNode node3 = new ListNode(5);ListNode node4 = new ListNode(6);ListNode node5 = new ListNode(2);//相交节点ListNode node6 = new ListNode(8);ListNode node7 = new ListNode(7);ListNode node8 = new ListNode(3);node1.next = node2; node2.next = node6; node6.next = node7; node7.next = node8;node3.next = node4; node4.next = node5; node5.next = node6;DoubleLoopNodes_06 test = new DoubleLoopNodes_06();ListNode n1 = test.getIntersectionNode(node1, node3);System.out.println("相交节点的值为 :" + (n1 != null ? n1.value : null));ListNode n2 = test.getIntersectionNode2(node1, node3);System.out.println("相交节点的值为 :" + (n2 != null ? n2.value : null));}
}
 

说了这么多,终极大boss终于要登场了。

题目7:给定两个可能有环也可能无环的单链表,头节点head1和head2。请实现一个函数,如果两个链表相交,请返回相交的 第一个节点。如果不相交,返回null

【要求】

如果两个链表长度之和为N,时间复杂度请达到O(N),额外空间复杂度 请达到O(1)

解题思路:根据排除所得,要么两条链表无环相交,要么有环相交,只存在这两种情况

package code03.链表_01;/*** 给定两个可能有环也可能无环的单链表,头节点head1和head2。请实现一个函数,如果两个链表相交,请返回相交的 第一个节点。如果不相交,返回null* 【要求】* 如果两个链表长度之和为N,时间复杂度请达到O(N),额外空间复杂度 请达到O(1)。** 解题思路:根据排除所得,要么两条链表无环相交,要么有环相交,只存在这两种情况*/
public class DoubleLoopNodes_06_2
{static class ListNode {int value;ListNode next;ListNode(int value) {this.value = value;}}//获取单链表相交的第一个节点,不想交则返回nullpublic ListNode getLoopNode(ListNode node){//需要使用快慢指针if (node == null || node.next == null || node.next.next == null) {return null;}ListNode fast = node.next.next;ListNode slow = node.next;//跳出当前循环//1) fast == slow 循环链表//2) fast.next 或 fast.next.next 为 null 不是循环链表while (fast.next != null && fast.next.next != null) {if (fast == slow) {break;}fast = fast.next.next;slow = slow.next;}//无环链表if (fast.next == null || fast.next.next == null) {return null;}//有环链表fast = node;//备注1: 找出第一个相交节点,此处根据数据推导公式得出while (fast != slow) {fast = fast.next;slow = slow.next;}//返回fast 或 slow 都对return fast;}//两个都没有循环链表的相交节点public ListNode bothNoCycleNodes(ListNode headA, ListNode headB){if (headA == null || headB == null) {return null;}ListNode cur = headA;int n = 0;while (cur != null) {n++;cur = cur.next;}cur = headB;while (cur != null) {n--;cur = cur.next;}ListNode lNode = n > 0 ? headA : headB;   //长链表ListNode sNode = lNode == headA ? headB : headA; //短链表n = Math.abs(n);while (n > 0) {lNode = lNode.next;n--;}//此刻,长链表剩下的节点和短链表剩下的节点个数相同while (lNode != sNode) {lNode = lNode.next;sNode = sNode.next;if(lNode == null || sNode == null) {return null;}}return lNode;}public ListNode bothCycleNodes(ListNode headA, ListNode loopA, ListNode headB,  ListNode loopB){//2种情况: 环外相交,正好第一个相交节点相交。 这种情况可以视为2个无环链表相交if (loopA == loopB) {int n = 0;ListNode cur = headA;while (cur != loopA) {n++;cur = cur.next;}cur = headB;while (cur != loopB) {n--;cur = cur.next;}ListNode lNode = n > 0 ? headA : headB;   //长链表ListNode sNode = lNode == headA ? headB : headA; //短链表n = Math.abs(n);while (n > 0) {lNode = lNode.next;n--;}//此刻,长链表剩下的节点和短链表剩下的节点个数相同while (lNode != sNode) {lNode = lNode.next;sNode = sNode.next;}return lNode;}else { //环内相交ListNode cur1 = loopA.next;while (cur1 != loopA) {  //如果跑一圈都没找到相交节点,则无相交节点if (cur1 == loopB) { //中途找到了相交节点return loopB;    //返回loopA 或 loopB 都行。 环内相交,说不清谁是第一个}cur1 = cur1.next;}return null;}}public ListNode getIntersectionNode (ListNode node1, ListNode node2){if (node1 == null || node2 == null) {return null;}ListNode loopNode1 = getLoopNode(node1);ListNode loopNode2 = getLoopNode(node2);ListNode ansNode = null;if (loopNode1 == null && loopNode2 == null) {  //两个都没有环的节点ansNode = bothNoCycleNodes(node1, node2);}else if (loopNode1 != null && loopNode2 != null) {  //两个环形链表相交ansNode = bothCycleNodes(node1,loopNode1, node2,loopNode2);}return  ansNode;}public static void main(String[] args) {System.out.println("================测试2个无环聊表相交===========================");//链表1ListNode node1 = new ListNode(4);ListNode node2 = new ListNode(1);//链表2ListNode node3 = new ListNode(5);ListNode node4 = new ListNode(6);ListNode node5 = new ListNode(2);//相交节点ListNode node6 = new ListNode(8);ListNode node7 = new ListNode(7);ListNode node8 = new ListNode(3);node1.next = node2; node2.next = node6; node6.next = node7; node7.next = node8;node3.next = node4; node4.next = node5;DoubleLoopNodes_06_2 test = new DoubleLoopNodes_06_2();//不相交ListNode m1 = test.getIntersectionNode(node1, node3);System.out.println("无环 不相交 :" + (m1 != null ? m1.value : null));//相交node5.next = node6;ListNode m2 = test.getIntersectionNode(node1, node3);System.out.println("无环 相交节点的值为 :" + (m2 != null ? m2.value : null));System.out.println("================测试2个环形链表 环外 相交===========================");//链表1ListNode n1 = new ListNode(4);ListNode n2 = new ListNode(1);//链表2ListNode n3 = new ListNode(5);ListNode n4 = new ListNode(6);ListNode n5 = new ListNode(2);//相交节点ListNode n6 = new ListNode(8);ListNode n7 = new ListNode(7);ListNode n8 = new ListNode(3);n1.next = n2; n2.next = n3; n3.next = n4; n4.next = n2;n5.next = n6; n6.next = n7; n7.next = n8; n8.next = n6;ListNode m3 = test.getIntersectionNode(n1, n5);System.out.println("有环  不相交 :" + (m3 != null ? m3.value : null));  //不相交n1.next = n2; n2.next = n3; n3.next = n4; n4.next = n5; n5.next = n3;n6.next = n7; n7.next = n8; n8.next = n3;ListNode m4 = test.getIntersectionNode(n1, n6);System.out.println("有环  第一个相交点相交 :" + (m4 != null ? m4.value : null));   //n3对应的值是5n1.next = n2; n2.next = n3; n3.next = n4; n4.next = n5; n5.next = n3;n6.next = n7; n7.next = n8; n8.next = n2;ListNode m5 = test.getIntersectionNode(n1, n6);System.out.println("有环  环外相交 :" + (m5 != null ? m5.value : null));   //n2对应的值是1System.out.println("================测试2个环形链表 环内 相交===========================");n6.next = n7; n7.next = n8; n8.next = n4;ListNode m6 = test.getIntersectionNode(n1, n6);System.out.println("有环  环外相交 :" + (m6 != null ? m6.value : null));   //n2对应的值是1 n4对应6}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_71896.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Netty (三):进阶

文章目录1. 粘包与半包1.1 粘包现象1.2 半包现象1.3 现象分析1.4 解决方案方法1&#xff0c;短链接方法2&#xff0c;固定长度方法3&#xff0c;固定分隔符方法4&#xff0c;预设长度2. 协议设计与解析2.1 为什么需要协议&#xff1f;2.2 redis 协议举例2.3 http 协议举例2.4 自…

前端二面react面试题集锦

react diff 算法 我们知道React会维护两个虚拟DOM&#xff0c;那么是如何来比较&#xff0c;如何来判断&#xff0c;做出最优的解呢&#xff1f;这就用到了diff算法 diff算法的作用 计算出Virtual DOM中真正变化的部分&#xff0c;并只针对该部分进行原生DOM操作&#xff0c;而…

「TCG 规范解读」第七章 TPM工作组 TPM 总结

可信计算组织&#xff08;Ttrusted Computing Group,TCG&#xff09;是一个非盈利的工业标准组织&#xff0c;它的宗旨是加强在相异计算机平台上的计算环境的安全性。TCG于2003年春成立&#xff0c;并采纳了由可信计算平台联盟&#xff08;the Trusted Computing Platform Alli…

【Azure 架构师学习笔记】-Azure Data Factory (1)-调度入门

本文属于【Azure 架构师学习笔记】系列。 本文属于【Azure Data Factory】系列。 前言 在开发好一个ADF pipeline&#xff08;功能&#xff09;之后&#xff0c;需要将其按需要运行起来&#xff0c;这个称之为调度。下图是一个简单的ADF 运作图&#xff0c; 按照需要的顺序&am…

【YOLOv5】 02-标注图片,训练并使用自己的模型

在上一篇文章中&#xff0c;我们完成了YOLOv5的安装和测试。如果想检测自定义目标&#xff0c;就需要用到LabelImg来对图片打标签&#xff0c;本篇文章介绍了LabelImg安装与使用&#xff0c;以及如何训练并使用自己的模型。一、安装LabelImg输入如下命令进行安装&#xff1a;pi…

seo优化案例截图

点击进入》》三支一扶课程聚合页面 百度统计数据 流量稳步增长&#xff0c; 2022年9月比2021年9月 同期增长 约30%。

rocketmq延时消息自定义配置;一个topic下tag分组

概述 使用的是开源版本的rocketmq4.9.4 rocketmq也是支持延时消息的。 rocketmq一般是4个部分&#xff1a; nameserver&#xff1a;保存路由信息broker&#xff1a;保存消息生产者&#xff1a;生产消息消费者&#xff1a;消费消息 延时消息的处理是在其中的broker中。 但是…

项目中异常信息的统一处理以及JSR03校验

在项目中&#xff0c;我们经常会对前端传过来的数据判断是否有一些错误&#xff0c;比如&#xff1a;id是否为空&#xff0c;传过来的名称是否合格&#xff0c;如果不符合我们通常会抛出异常&#xff0c;那么小的项目可能每次抛出异常也不是很麻烦&#xff0c;但是对于一个大型…

小程序上新(2022.12.12~2023.02.20)

20221216关于小程序违规收集用户隐私行为的规范20221222优先使用本地版本设置功能上线备注:已和微信官方工作人员确认,开启本地优先后&#xff0c;用户打开小程序过程中&#xff0c;异步去下载新版包&#xff0c;打开完成后&#xff0c;功能是新包,异步下载完成后提示用户重启小…

actipro-winforms-controls-23.1.0 Crack

actipro-winforms一组用于构建漂亮的 Windows 窗体桌面应用程序的 UI 控件&#xff0c;用于构建 IDE 的高级停靠窗口、MDI、属性网格、树控件和文件夹/文件浏览器&#xff0c;用于常见数据类型、自动完成、屏蔽编辑和代码编辑的强大编辑器&#xff0c;功能区、图表、微型图表、…

JavaScript中怎么实现链表?

JavaScript中怎么实现链表&#xff1f; 学习数据结构的的链表和树时&#xff0c;会遇到节点&#xff08;node&#xff09;这个词&#xff0c;节点是处理数据结构的链表和树的基础。节点是一种数据元素&#xff0c;包括两个部分&#xff1a;一个是实际需要用到的数据&#xff1b…

十一、项目实战一

项目实战一 需求 以 前后端不分离的方式实现学生的增删改查操作 学生列表功能 接口设计 url:/students/ 请求方法&#xff1a;get 参数&#xff1a; 格式&#xff1a;查询参数 参数名类型是否必传说明pageint否页码&#xff0c;默认为1sizeinit否每页数据条数默认为10n…

Ansys Zemax | 如何在存在全内反射 (TIR) 的情况下应用散射

在本文中&#xff0c;我们将展示如何利用虚拟表面来对具有全内反射 (TIR) 的物体进行建模&#xff0c;同时保持其他独特的表面特性&#xff0c;例如粗糙的表面结构。 下载 联系工作人员获取附件 简介 在OpticStudio中&#xff0c;全内反射 (TIR) 在其他表面属性&#xff08…

Java:顶级Java应用程序服务器 — Tomcat、Jetty、GlassFish、WildFly

如果你想编写Java web应用程序&#xff0c;首先需要做出一个艰难的决定&#xff1a;选择运行应用程序的Java应用程序服务器。什么是应用服务器?一般来说&#xff0c;应用程序服务器执行Java应用程序。在操作系统中启动它们&#xff0c;然后将应用程序部署到其中。将应用程序服…

07 二叉树

开始系统学习算法啦&#xff01;为后面力扣和 蓝桥杯的刷题做准备&#xff01;这个专栏将记录自己学习算法是的笔记&#xff0c;包括 概念&#xff0c; 算法运行过程&#xff0c;以及 代码实现&#xff0c;希望能给大家带来帮助&#xff0c;感兴趣的小伙伴欢迎评论区留言或者私…

重要节点排序方法

文章目录研究背景提前约定基于节点近邻的排序方法度中心性&#xff08;degree centrality, DC&#xff09;半局部中心性&#xff08;semilocal centrality, SLC&#xff09;k-壳分解法基于路径排序的方法离心中心性 (Eccentricity, ECC)接近中心性 (closeness centrality, CC)K…

【图文详解】Unity存储游戏数据的几种方法

Unity3D存储游戏数据的方式1 PlayerPrefs: Unity自带的一种简单的键值存储系统2 ScriptableObject: Unity中最灵活的数据管理工具2.1 如何手动创建和修改数据文件2.2 ScriptableObject优缺点总结3 JSON: 轻量级的数据交换格式3.1 序列化与反序列化3.2 用JsonUtility对对象进行序…

最好的工程师像投资者一样思考,而不是建设者

我在大学期间住在图书馆。“我学习的教科书理论越多&#xff0c;我就会成为一名更好的工程师&#xff0c;”我想。然而&#xff0c;当我开始工作时&#xff0c;我注意到业内最优秀的工程师并不一定比应届毕业生了解更多的理论。他们只是带来了不同的心态&#xff0c;即投资者的…

STM32单片机蓝牙APP空气净化系统甲醛二氧化碳温度SGP30

实践制作DIY- GC0124-蓝牙APP空气净化系统 一、功能说明&#xff1a; 基于STM32单片机设计-蓝牙APP空气净化系统 功能介绍&#xff1a; 硬件组成&#xff1a;STM32F103C最小系统板DS18B20温度传感器OLEDSGP二氧化碳甲醛传感器5V直流风扇多个按键HC-05蓝牙模块&#xff08;仅蓝…

大数据框架之Hadoop:MapReduce(三)MapReduce框架原理——MapReduce工作流程

1、流程示意图 MapReduce详细工作流程&#xff08;一&#xff09; MapReduce详细工作流程&#xff08;二&#xff09; 2、流程详解 上面的流程是整个MapReduce最全工作流程&#xff0c;但是Shuffle过程只是从第7步开始到第16步结束&#xff0c;具体Shuffle过程详解&#xff0…