写点什么

第八周作业

用户头像
Meow
关注
发布于: 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);
}
}



用户头像

Meow

关注

还未添加个人签名 2018.05.09 加入

还未添加个人简介

评论

发布
暂无评论
第八周作业