第八周作业
发布于: 2020 年 11 月 15 日
作业一:
(至少完成一个)
有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,也可能不合并,如下图所示的这样。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。
请用代码(或伪代码)描述算法,并给出时间复杂度。
package week8;/** * @program: GeekTest * @description: * @author: Meow_Young * @created: 2020/11/15 17:40 */public class SinglyLinkedList { 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 getLoopNode(Node head) { if (head == null || head.next == null || head.next.next == null) { return null; } /*n1 -> slow*/ Node n1 = head.next; /*n2 -> fast*/ Node n2 = head.next.next; while (n1 != n2) { if (n2.next == null || n2.next.next == null) { return null; } n2 = n2.next.next; n1 = n1.next; } /*n2 -> walk again from head*/ n2 = 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[]){ //侧重算法,没有实现链表部分 Node node1 = new Node(1); Node node2 = new Node(2); Node node3 = new Node(3); Node node4 = new Node(4); Node node5 = new Node(5); Node node6 = new Node(6); Node node7 = new Node(7); node1.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; node5.next = node6; node6.next = node7; node7.next = node4; Node node11 = new Node(0); Node node22 = new Node(9); Node node33 = new Node(8); node11.next = node22; node22.next = node33; node33.next = node6; Node result = getIntersectNode(node1,node11); System.out.print(result.value); }}
划线
评论
复制
发布于: 2020 年 11 月 15 日阅读数: 23
Meow
关注
还未添加个人签名 2018.05.09 加入
还未添加个人简介
评论