接着前面的内容
这次主要讨论链表相关的题目
机试的时候怎么快怎么做, 面试的时候要聊时间 O(N), 额外空间复杂度达到 O(1).
题目十
打印两个有序链表的公共部分
[题目] 给定两个有序链表的头指针 head1 和 head2, 打印两个链表的公共部分.
- public class Code_10_PrintCommonPart {
- public static class Node {
- public int value;
- public Node next;
- public Node(int data) {
- this.value = data;
- }
- }
- public static void printCommonPart(Node head1, Node head2) {
- System.out.print("Common Part:");
- while (head1 != null && head2 != null) {
- if (head1.value <head2.value) {
- head1 = head1.next;
- } else if (head1.value> head2.value) {
- head2 = head2.next;
- } else {
- System.out.print(head1.value + " ");
- head1 = head1.next;
- head2 = head2.next;
- }
- }
- System.out.println();
- }
- public static void printLinkedList(Node node) {
- System.out.print("Linked List:");
- while (node != null) {
- System.out.print(node.value + " ");
- node = node.next;
- }
- System.out.println();
- }
- public static void main(String[] args) {
- Node node1 = new Node(2);
- node1.next = new Node(3);
- node1.next.next = new Node(5);
- node1.next.next.next = new Node(6);
- Node node2 = new Node(1);
- node2.next = new Node(2);
- node2.next.next = new Node(5);
- node2.next.next.next = new Node(7);
- node2.next.next.next.next = new Node(8);
- printLinkedList(node1);
- printLinkedList(node2);
- printCommonPart(node1, node2);
- }
- }
题目十一
判断一个链表是否为回文结构
[题目] 给定一个链表的头节点 head, 请判断该链表是否为回文结构. 例如: 1->2->1, 返回 true. 1->2->2->1, 返回 true.15->6->15, 返回 true. 1->2->3, 返回 false.
进阶: 如果链表长度为 N, 时间复杂度达到 O(N), 额外空间复杂度达到 O(1).
方法一: 放到栈里面再逆序比对 (利用额外空间)
方法二: 两个指针, 1 走一步, 2 走两步, 2 到了终点, 1 就到了中点, 然后 1 往后的压栈, 在逐一比对.
方法三:(额外空间 O(1)): 先通过快慢指针, 找到中点, 然后改变中间后面的链表的指向, 在逐一比对, 最后再把指针还原如初.
- public class Code_11_IsPalindromeList {
- public static class Node {
- public int value;
- public Node next;
- public Node(int data) {
- this.value = data;
- }
- }
- // need n extra space
- public static boolean isPalindrome1(Node head) {
- Stack<Node> stack = new Stack<Node>();
- Node cur = head;
- while (cur != null) {
- stack.push(cur);
- cur = cur.next;
- }
- while (head != null) {
- if (head.value != stack.pop().value) {
- return false;
- }
- head = head.next;
- }
- return true;
- }
- // need n/2 extra space
- public static boolean isPalindrome2(Node head) {
- if (head == null || head.next == null) {
- return true;
- }
- // 慢指针, 提前走一步为了当链表为奇数时走在中间区域的最后一个数
- // 也方便了直接存入在对比的栈当中
- Node slow = head.next;
- // 快指针
- Node fast = head;
- while (fast.next != null && fast.next.next != null) {
- slow = slow.next;
- fast = fast.next.next;
- }
- Stack<Node> stack = new Stack<Node>();
- while (slow != null) {
- stack.push(slow);
- slow = slow.next;
- }
- while (!stack.isEmpty()) {
- if (head.value != stack.pop().value) {
- return false;
- }
- head = head.next;
- }
- return true;
- }
- // need O(1) extra space
- public static boolean isPalindrome3(Node head) {
- if (head == null || head.next == null) {
- return true;
- }
- Node n1 = head;
- Node n2 = head;
- while (n2.next != null && n2.next.next != null) { // find mid node
- n1 = n1.next; // n1 -> mid
- n2 = n2.next.next; // n2 -> end
- }
- n2 = n1.next; // n2 -> right part first node
- n1.next = null; // mid.next -> null
- Node n3 = null;
- while (n2 != null) { // right part convert
- n3 = n2.next; // n3 -> save next node 操作前先保存下一个节点
- n2.next = n1; // next of right node convert 反转指向
- n1 = n2; // n1 move 保存当前节点, 作为后一个的前节点
- n2 = n3; // n2 move 向前推进
- }
- n3 = n1; // n3 -> save last node
- n2 = head;// n2 -> left first node
- boolean res = true;
- while (n1 != null && n2 != null) { // check palindrome
- if (n1.value != n2.value) {
- res = false;
- break;
- }
- n1 = n1.next; // left to mid
- n2 = n2.next; // right to mid
- }
- n1 = n3.next;
- n3.next = null;
- while (n1 != null) { // recover list
- n2 = n1.next;
- n1.next = n3;
- n3 = n1;
- n1 = n2;
- }
- return res;
- }
- public static void printLinkedList(Node node) {
- System.out.print("Linked List:");
- while (node != null) {
- System.out.print(node.value + " ");
- node = node.next;
- }
- System.out.println();
- }
- public static void main(String[] args) {
- Node head = null;
- printLinkedList(head);
- System.out.print(isPalindrome1(head) + "|");
- System.out.print(isPalindrome2(head) + "|");
- System.out.println(isPalindrome3(head) + "|");
- printLinkedList(head);
- System.out.println("=========================");
- head = new Node(1);
- printLinkedList(head);
- System.out.print(isPalindrome1(head) + "|");
- System.out.print(isPalindrome2(head) + "|");
- System.out.println(isPalindrome3(head) + "|");
- printLinkedList(head);
- System.out.println("=========================");
- head = new Node(1);
- head.next = new Node(2);
- printLinkedList(head);
- System.out.print(isPalindrome1(head) + "|");
- System.out.print(isPalindrome2(head) + "|");
- System.out.println(isPalindrome3(head) + "|");
- printLinkedList(head);
- System.out.println("=========================");
- head = new Node(1);
- head.next = new Node(1);
- printLinkedList(head);
- System.out.print(isPalindrome1(head) + "|");
- System.out.print(isPalindrome2(head) + "|");
- System.out.println(isPalindrome3(head) + "|");
- printLinkedList(head);
- System.out.println("=========================");
- head = new Node(1);
- head.next = new Node(2);
- head.next.next = new Node(3);
- printLinkedList(head);
- System.out.print(isPalindrome1(head) + "|");
- System.out.print(isPalindrome2(head) + "|");
- System.out.println(isPalindrome3(head) + "|");
- printLinkedList(head);
- System.out.println("=========================");
- head = new Node(1);
- head.next = new Node(2);
- head.next.next = new Node(1);
- printLinkedList(head);
- System.out.print(isPalindrome1(head) + "|");
- System.out.print(isPalindrome2(head) + "|");
- System.out.println(isPalindrome3(head) + "|");
- printLinkedList(head);
- System.out.println("=========================");
- head = new Node(1);
- head.next = new Node(2);
- head.next.next = new Node(3);
- head.next.next.next = new Node(1);
- printLinkedList(head);
- System.out.print(isPalindrome1(head) + "|");
- System.out.print(isPalindrome2(head) + "|");
- System.out.println(isPalindrome3(head) + "|");
- printLinkedList(head);
- System.out.println("=========================");
- head = new Node(1);
- head.next = new Node(2);
- head.next.next = new Node(2);
- head.next.next.next = new Node(1);
- printLinkedList(head);
- System.out.print(isPalindrome1(head) + "|");
- System.out.print(isPalindrome2(head) + "|");
- System.out.println(isPalindrome3(head) + "|");
- printLinkedList(head);
- System.out.println("=========================");
- head = new Node(1);
- head.next = new Node(2);
- head.next.next = new Node(3);
- head.next.next.next = new Node(2);
- head.next.next.next.next = new Node(1);
- printLinkedList(head);
- System.out.print(isPalindrome1(head) + "|");
- System.out.print(isPalindrome2(head) + "|");
- System.out.println(isPalindrome3(head) + "|");
- printLinkedList(head);
- System.out.println("=========================");
- }
- }
题目十二
将单向链表按某值划分成左边小, 中间相等, 右边大的形式
[题目] 给定一个单向链表的头节点 head, 节点的值类型是整型, 再给定一个整 数 pivot. 实现一个调整链表的函数, 将链表调整为左部分都是值小于 pivot 的节点, 中间部分都是值等于 pivot 的节点, 右部分都是值大于 pivot 的节点. 除这个要求外, 对调整后的节点顺序没有更多的要求. 例如: 链表 9->0->4->5->1,pivot=3. 调整后链表可以是 1->0->4->9->5, 也可以是 0->1->9->5->4. 总之, 满 足左部分都是小于 3 的节点, 中间部分都是等于 3 的节点 (本例中这个部分为空), 右部分都是大于 3 的节点即可. 对某部分内部的节点顺序不做 要求.
可以使用荷兰国旗的方法去处理, 数组每个元素变为结点类型, 然后再接起来.
进阶: 在原问题的要求之上再增加如下两个要求.
在左, 中, 右三个部分的内部也做顺序要求, 要求每部分里的节点从左 到右的顺序与原链表中节点的先后次序一致. 例如: 链表 9->0->4->5->1,pivot=3. 调整后的链表是 0->1->9->4->5. 在满足原问题要求的同时, 左部分节点从左到右为 0,1. 在原链表中也 是先出现 0, 后出现 1; 中间部分在本例中为空, 不再讨论; 右部分节点 从左到右为 9,4,5. 在原链表中也是先出现 9, 然后出现 4, 最后出现 5.
如果链表长度为 N, 时间复杂度请达到 O(N), 额外空间复杂度请达到 O(1).
准备三个变量, 这三个变量都是节点对象的引用类型. Less eq more
先遍历链表, 找到第一个小于 / 等于 / 大于 num 的节点, 让 Less/eq/more 等于那个节点.
然后准备多一个 end, 每次加入一个, end 就加一, 直到最后把三个小链表头尾链接起来.
(原理是把一个大链表, 拆成三个小链表, 再组装起来) 有限几个变量 O(1).
- public class Code_12_SmallerEqualBigger {
- public static class Node {
- public int value;
- public Node next;
- public Node(int data) {
- this.value = data;
- }
- }
- public static Node listPartition1(Node head, int pivot) {
- if (head == null) {
- return head;
- }
- Node cur = head;
- int i = 0;
- while (cur != null) {
- i++;
- cur = cur.next;
- }
- Node[] nodeArr = new Node[i];
- i = 0;
- cur = head;
- for (i = 0; i != nodeArr.length; i++) {
- nodeArr[i] = cur;
- cur = cur.next;
- }
- arrPartition(nodeArr, pivot);
- for (i = 1; i != nodeArr.length; i++) {
- nodeArr[i - 1].next = nodeArr[i];
- }
- nodeArr[i - 1].next = null;
- return nodeArr[0];
- }
- public static void arrPartition(Node[] nodeArr, int pivot) {
- int small = -1;
- int big = nodeArr.length;
- int index = 0;
- while (index != big) {
- if (nodeArr[index].value <pivot) {
- swap(nodeArr, ++small, index++);
- } else if (nodeArr[index].value == pivot) {
- index++;
- } else {
- swap(nodeArr, --big, index);
- }
- }
- }
- public static void swap(Node[] nodeArr, int a, int b) {
- Node tmp = nodeArr[a];
- nodeArr[a] = nodeArr[b];
- nodeArr[b] = tmp;
- }
- public static Node listPartition2(Node head, int pivot) {
- Node sH = null; // small head
- Node sT = null; // small tail
- Node eH = null; // equal head
- Node eT = null; // equal tail
- Node bH = null; // big head
- Node bT = null; // big tail
- Node next = null; // save next node
- // every node distributed to three lists
- while (head != null) {
- next = head.next;
- head.next = null;
- if (head.value < pivot) {
- if (sH == null) {
- sH = head;
- sT = head;
- } else {
- sT.next = head;
- sT = head;
- }
- } else if (head.value == pivot) {
- if (eH == null) {
- eH = head;
- eT = head;
- } else {
- eT.next = head;
- eT = head;
- }
- } else {
- if (bH == null) {
- bH = head;
- bT = head;
- } else {
- bT.next = head;
- bT = head;
- }
- }
- head = next;
- }
- // small and equal reconnect
- if (sT != null) {
- sT.next = eH;
- eT = eT == null ? sT : eT;
- }
- // all reconnect
- if (eT != null) {
- eT.next = bH;
- }
- return sH != null ? sH : eH != null ? eH : bH;
- }
- public static void printLinkedList(Node node) {
- System.out.print("Linked List:");
- while (node != null) {
- System.out.print(node.value + " ");
- node = node.next;
- }
- System.out.println();
- }
- 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);
- printLinkedList(head1);
- // head1 = listPartition1(head1, 4);
- head1 = listPartition2(head1, 5);
- printLinkedList(head1);
- }
- }
题目十三
复制含有随机指针节点的链表
[题目] 一种特殊的链表节点类描述如下:
- public class Node {
- public int value;
- public Node next;
- public Node rand;
- public Node(int data) {this.value = data;}
- }
Node 类中的 value 是节点值, next 指针和正常单链表中 next 指针的意义一 样, 都指向下一个节点, rand 指针是 Node 类中新增的指针, 这个指针可 能指向链表中的任意一个节点, 也可能指向 null. 给定一个由 Node 节点类型组成的无环单链表的头节点 head, 请实现一个 函数完成这个链表中所有结构的复制, 并返回复制的新链表的头节点.
进阶: 不使用额外的数据结构, 只用有限几个变量, 且在时间复杂度为 O(N) 内完成原问题要实现的函数.
方法一: 准备一个 hashmap, 依次把结点作为 key, 复制的结点为 value 存入. 然后再通过 key 查找 value 的方式, 复制指针的指向, 达到深入拷贝.
进阶方法: 不用 hashmap 的方法, 先遍历一遍原链表, 形成 1-->1'--->2... 的结构, 然后利用 1-->random 指引 1'-->random 的连接, 连完再分离.
- public class Code_13_CopyListWithRandom {
- public static class Node {
- public int value;
- public Node next;
- public Node rand;
- public Node(int data) {
- this.value = data;
- }
- }
- public static Node copyListWithRand1(Node head) {
- HashMap<Node, Node> map = new HashMap<Node, Node>();
- Node cur = head;
- while (cur != null) {
- map.put(cur, new Node(cur.value));
- cur = cur.next;
- }
- cur = head;
- while (cur != null) {
- map.get(cur).next = map.get(cur.next);
- map.get(cur).rand = map.get(cur.rand);
- cur = cur.next;
- }
- return map.get(head);
- }
- public static Node copyListWithRand2(Node head) {
- if (head == null) {
- return null;
- }
- Node cur = head;
- Node next = null;
- // copy node and link to every node
- // 先遍历一遍原链表, 形成 1-->1'--->2... 的结构
- while (cur != null) {
- next = cur.next;
- cur.next = new Node(cur.value);
- cur.next.next = next;
- cur = next;
- }
- cur = head;
- Node curCopy = null;
- // set copy node rand
- // 复制随机指针
- while (cur != null) {
- next = cur.next.next;
- curCopy = cur.next;
- //// 存在一种情况, 末尾的随机指针指向为空, 再引用空的下一个就会报错
- curCopy.rand = cur.rand != null ? cur.rand.next : null;
- cur = next;
- }
- Node res = head.next;
- cur = head;
- // split
- // 分离的同时, 顺便重连链表
- while (cur != null) {
- next = cur.next.next;//2 null
- curCopy = cur.next;//1'3'
- cur.next = next;//2 null
- // 需要判断后续是否还有节点的存在
- curCopy.next = next != null ? next.next : null;//2'
- cur = next;//2
- }
- return res;
- }
- public static void printRandLinkedList(Node head) {
- Node cur = head;
- System.out.print("order:");
- while (cur != null) {
- System.out.print(cur.value + " ");
- cur = cur.next;
- }
- System.out.println();
- cur = head;
- System.out.print("rand:");
- while (cur != null) {
- System.out.print(cur.rand == null ? "-" : cur.rand.value + " ");
- cur = cur.next;
- }
- System.out.println();
- }
- public static void main(String[] args) {
- Node head = null;
- Node res1 = null;
- Node res2 = null;
- printRandLinkedList(head);
- res1 = copyListWithRand1(head);
- printRandLinkedList(res1);
- res2 = copyListWithRand2(head);
- printRandLinkedList(res2);
- printRandLinkedList(head);
- System.out.println("=========================");
- head = new Node(1);
- head.next = new Node(2);
- head.next.next = new Node(3);
- head.next.next.next = new Node(4);
- head.next.next.next.next = new Node(5);
- head.next.next.next.next.next = new Node(6);
- head.rand = head.next.next.next.next.next; // 1 -> 6
- head.next.rand = head.next.next.next.next.next; // 2 -> 6
- head.next.next.rand = head.next.next.next.next; // 3 -> 5
- head.next.next.next.rand = head.next.next; // 4 -> 3
- head.next.next.next.next.rand = null; // 5 -> null
- head.next.next.next.next.next.rand = head.next.next.next; // 6 -> 4
- printRandLinkedList(head);
- res1 = copyListWithRand1(head);
- printRandLinkedList(res1);
- res2 = copyListWithRand2(head);
- printRandLinkedList(res2);
- printRandLinkedList(head);
- System.out.println("=========================");
- }
- }
题目十四
两个单链表相交的一系列问题
[题目] 在本题中, 单链表可能有环, 也可能无环. 给定两个单链表的头节点 head1 和 head2, 这两个链表可能相交, 也可能不相交. 请实现一个函数, 如果两个链表相交, 请返回相交的第一个节点; 如果不相交, 返回 null 即可.
要求: 如果链表 1 的长度为 N, 链表 2 的长度为 M, 时间复杂度请达到 O(N+M), 额外空间复杂度请达到 O(1).
首先解决判断是否有环, 利用 hashset 来做 (有环就返回第一个入环的结点)
- public static Node getLoopNodeByHashMap(Node head){
- if(head == null || head.next == null||head.next.next==null ){
- return null;
- }
- HashSet<Node> nodeset = new HashSet<>();
- while (head!=null){
- if(nodeset.contains(head)){
- return head;
- }
- nodeset.add(head);
- head = head.next;
- }
- return null;
- }
不用 hash 表要怎么做? 准备两个指针, 一快一慢, 快一次两步, 慢一次一步, 如果快指针走到 null 直接返回无环.
如果快指针和慢指针相遇, 证明有环, 相遇后, 快指针回到起点, 快指针从一次两步变一次一步, 快指针和慢指针一定在第一个入环结点处相遇.(数学归纳法)(玄学)
- public static Node getLoopNode(Node head) {
- if (head == null || head.next == null || head.next.next == null) {
- return null;
- }
- Node n1 = head.next; // n1 -> slow
- Node n2 = head.next.next; // n2 -> fast
- while (n1 != n2) {
- if (n2.next == null || n2.next.next == null) {
- return null;
- }
- n2 = n2.next.next;
- n1 = n1.next;
- }
- n2 = head; // n2 -> walk again from head
- while (n1 != n2) {
- n1 = n1.next;
- n2 = n2.next;
- }
- return n1;
- }
判断链表是否相交:
使用 map 查看两个无环链表是否相交, 先链表 1 放入 map, 然后遍历链表 2, 第一个出现在 map 中的就是相交的节点, 否则没有就不相交.
Loop 是第一个入环的结点.
- public static Node noLoopByHashSet(Node head1, Node head2) {
- if (head1 == null || head2 == null) {
- return null;
- }
- HashSet<Node> NodeSet = new HashSet<>();
- while (head1 != null) {
- NodeSet.add(head1);
- head1 = head1.next;
- }
- while (head2 != null) {
- if (NodeSet.contains(head2)) {
- return head2;
- }
- head2 = head2.next;
- }
- return null;
- }
不用 Map 怎么做? 遍历链表 1 统计长度, 并拿到链表 1 最后一个节点. 链表 2 同上操作.
接着判断 end1 和 end2 内存地址是否一致, 如果不相等, 他们不可能相交.
如果相等, 证明相交, 但是不证明这是他们第一个相交的节点.
当相等时候, 进行利用长度进行后序的操作
例如: 1 长为 100,2 为 80, 那么 1 先走 20 步
然后和 2 一起走, 他们肯定能走到第一个相会处.
- public static Node noLoop(Node head1, Node head2) {
- if (head1 == null || head2 == null) {
- return null;
- }
- Node cur1 = head1;
- Node cur2 = head2;
- int n = 0;
- while (cur1.next != null) {
- n++;
- cur1 = cur1.next;
- }
- while (cur2.next != null) {
- n--;
- cur2 = cur2.next;
- }
- if (cur1 != cur2) {
- return null;
- }
- cur1 = n> 0 ? head1 : head2;// 找出哪个比较长
- cur2 = cur1 == head1 ? head2 : head1;
- n = Math.abs(n);
- while (n != 0) {// 较长的先走
- n--;
- cur1 = cur1.next;
- }
- while (cur1 != cur2) {
- cur1 = cur1.next;
- cur2 = cur2.next;
- }
- return cur1;
- }
如果一个有环一个无环? 结论: 不可能相交
两个有环链表相交, 怎么找到第一个入环的节点?
有三种拓扑结构,
当 loop1==loop2(loop 是第一个入环的节点) 时候, 是第二种 (可以复用无环链表相交问题的处理逻辑)
如果不相等可能是结构一或者三, 怎么区分? 第一个 loop1 一直 next 如果一直这样都转回自己了, 还没遇到 loop2 就是第一种拓扑.(不相交, 返回空)
如果他遇到了 loop2, 就是第三种拓扑. 此时返回 loop1/2 作为相交的节点都对.
- public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
- Node cur1 = null;
- Node cur2 = null;
- if (loop1 == loop2) {
- cur1 = head1;
- cur2 = head2;
- int n = 0;
- while (cur1 != loop1) {
- n++;
- cur1 = cur1.next;
- }
- while (cur2 != loop2) {
- n--;
- cur2 = cur2.next;
- }
- cur1 = n> 0 ? head1 : head2;
- cur2 = cur1 == head1 ? head2 : head1;
- n = Math.abs(n);
- while (n != 0) {
- n--;
- cur1 = cur1.next;
- }
- while (cur1 != cur2) {
- cur1 = cur1.next;
- cur2 = cur2.next;
- }
- return cur1;
- } else {
- cur1 = loop1.next;
- while (cur1 != loop1) {
- if (cur1 == loop2) {
- return loop1;
- }
- cur1 = cur1.next;
- }
- return null;
- }
- }
两链表相交的一系列问题全部代码 (包含测试代码)
- public class Code_14_FindFirstIntersectNode {
- public static class Node {
- public int value;
- public Node next;
- public Node(int data) {
- this.value = data;
- }
- }
- public static Node getIntersectNode(Node head1, Node head2) {
- if (head1 == null || head2 == null) {
- return null;
- }
- Node loop1 = getLoopNode(head1);
- Node loop2 = getLoopNode(head2);
- if (loop1 == null && loop2 == null) {
- return noLoop(head1, head2);
- }
- if (loop1 != null && loop2 != null) {
- return bothLoop(head1, loop1, head2, loop2);
- }
- return null;
- }
- public static Node getLoopNodeByHashMap(Node head){
- if(head == null || head.next == null||head.next.next==null ){
- return null;
- }
- HashSet<Node> nodeset = new HashSet<>();
- while (head!=null){
- if(nodeset.contains(head)){
- return head;
- }
- nodeset.add(head);
- head = head.next;
- }
- return null;
- }
- public static Node getLoopNode(Node head) {
- if (head == null || head.next == null || head.next.next == null) {
- return null;
- }
- Node n1 = head.next; // n1 -> slow
- Node n2 = head.next.next; // n2 -> fast
- while (n1 != n2) {
- if (n2.next == null || n2.next.next == null) {
- return null;
- }
- n2 = n2.next.next;
- n1 = n1.next;
- }
- n2 = head; // n2 -> walk again from head
- while (n1 != n2) {
- n1 = n1.next;
- n2 = n2.next;
- }
- return n1;
- }
- public static Node noLoop(Node head1, Node head2) {
- if (head1 == null || head2 == null) {
- return null;
- }
- Node cur1 = head1;
- Node cur2 = head2;
- int n = 0;
- while (cur1.next != null) {
- n++;
- cur1 = cur1.next;
- }
- while (cur2.next != null) {
- n--;
- cur2 = cur2.next;
- }
- if (cur1 != cur2) {
- return null;
- }
- cur1 = n> 0 ? head1 : head2;// 找出哪个比较长
- cur2 = cur1 == head1 ? head2 : head1;
- n = Math.abs(n);
- while (n != 0) {// 较长的先走
- n--;
- cur1 = cur1.next;
- }
- while (cur1 != cur2) {
- cur1 = cur1.next;
- cur2 = cur2.next;
- }
- return cur1;
- }
- public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
- Node cur1 = null;
- Node cur2 = null;
- if (loop1 == loop2) {
- cur1 = head1;
- cur2 = head2;
- int n = 0;
- while (cur1 != loop1) {
- n++;
- cur1 = cur1.next;
- }
- while (cur2 != loop2) {
- n--;
- cur2 = cur2.next;
- }
- cur1 = n> 0 ? head1 : head2;
- cur2 = cur1 == head1 ? head2 : head1;
- n = Math.abs(n);
- while (n != 0) {
- n--;
- cur1 = cur1.next;
- }
- while (cur1 != cur2) {
- cur1 = cur1.next;
- cur2 = cur2.next;
- }
- return cur1;
- } else {
- cur1 = loop1.next;
- while (cur1 != loop1) {
- if (cur1 == loop2) {
- return loop1;
- }
- cur1 = cur1.next;
- }
- return null;
- }
- }
- public static void main(String[] args) {
- // 1->2->3->4->5->6->7->null
- Node head1 = new Node(1);
- head1.next = new Node(2);
- head1.next.next = new Node(3);
- head1.next.next.next = new Node(4);
- head1.next.next.next.next = new Node(5);
- head1.next.next.next.next.next = new Node(6);
- head1.next.next.next.next.next.next = new Node(7);
- // 0->9->8->6->7->null
- Node head2 = new Node(0);
- head2.next = new Node(9);
- head2.next.next = new Node(8);
- head2.next.next.next = head1.next.next.next.next.next; // 8->6
- System.out.println(getIntersectNode(head1, head2).value);
- // 1->2->3->4->5->6->7->4...
- head1 = new Node(1);
- head1.next = new Node(2);
- head1.next.next = new Node(3);
- head1.next.next.next = new Node(4);
- head1.next.next.next.next = new Node(5);
- head1.next.next.next.next.next = new Node(6);
- head1.next.next.next.next.next.next = new Node(7);
- head1.next.next.next.next.next.next = head1.next.next.next; // 7->4
- // 0->9->8->2...
- head2 = new Node(0);
- head2.next = new Node(9);
- head2.next.next = new Node(8);
- head2.next.next.next = head1.next; // 8->2
- System.out.println(getIntersectNode(head1, head2).value);
- // 0->9->8->6->4->5->6..
- head2 = new Node(0);
- head2.next = new Node(9);
- head2.next.next = new Node(8);
- head2.next.next.next = head1.next.next.next.next.next; // 8->6
- System.out.println(getIntersectNode(head1, head2).value);
- }
- }
来源: https://www.cnblogs.com/xieyupeng/p/10279767.html