架构师训练营 第八周 课后练习

用户头像
且听且吟
关注
发布于: 2020 年 07 月 24 日

作业

有两个单向链表(链表长度分别为m,n),这两个单向链表有可能在某个元素合并,如下图所示的那样,也有可能不合并。现在给定两个链表的头指针,在不修改链表的情况下,如何快读的判断这两个链表是否合并?如果合并,找到合并的元素,也就是途中的x元素。请用(伪)代码描述算法,给出时间复杂度和空间复杂度。

图1 链表结构

代码结构

图2 源代码结构

源代码

package com.xianyanyang.linklist.node;
/**
* 链表节点
*/
public class LinkNode {
/**
* 链表节点地址
*/
private String address;
/**
* 链表节点的下一个节点
*/
private LinkNode next;
public LinkNode(String address) {
this.address = address;
}
public void setNext(LinkNode next) {
this.next = next;
}
public String getAddress() {
return address;
}
public LinkNode getNext() {
return next;
}
/**
* 是否拥有下一个节点
*
* @return 下一个节点
*/
public boolean hasNext() {
return next != null;
}
/**
* 是否是同一个节点
*
* @param otherNode 另一个节点
* @return 是否是同一个节点
*/
public boolean addressSameWith(LinkNode otherNode) {
return otherNode != null && otherNode.getAddress() != null && otherNode.getAddress().equals(address);
}
public LinkNode moveNext(int i) {
if (i == 0) {
return this;
}
LinkNode node = this;
while (i > 0) {
node = node.getNext();
i--;
}
return node;
}
}



package com.xianyanyang.linklist.calculator;
import com.xianyanyang.linklist.node.LinkNode;
/**
* 链表的合并交叉节点计算器
*/
public class ConnectiveNodeCalculator {
@Deprecated
public LinkNode calculateConnectiveNodeV1(LinkNode head1, LinkNode head2) {
if (!head1.hasNext()) {
System.out.println("未找到合并的元素");
return null;
}
if (!head2.hasNext()) {
System.out.println("未找到合并的元素");
return null;
}
LinkNode node1 = head1;
LinkNode node2 = head2;
while (node1.hasNext()) {
System.out.println("链表1节点" + node1.getAddress() + "->" + node1.getNext().getAddress());
node1 = node1.getNext();
while (node2.hasNext()) {
System.out.println("链表2节点" + node2.getAddress() + "->" + node2.getNext().getAddress());
node2 = node2.getNext();
if (node1.addressSameWith(node2)) {
System.out.println("合并的元素为" + node1.getAddress());
return node1;
}
}
System.out.println("-----------");
node2 = head2;
}
System.out.println("未找到合并的元素");
return null;
}
/**
* 查找两个链表的合并交叉节点
*
* @param head1 链表1的头节点
* @param head2 链表2的头节点
* @return 合并交叉节点
*/
public LinkNode calculateConnectiveNodeV2(LinkNode head1, LinkNode head2) {
if (!head1.hasNext()) {
System.out.println("未找到合并的元素");
return null;
}
if (!head2.hasNext()) {
System.out.println("未找到合并的元素");
return null;
}
LinkNode lastNode1 = findNodeLastNode(head1);
LinkNode lastNode2 = findNodeLastNode(head2);
if (!lastNode1.addressSameWith(lastNode2)) {
System.out.println("未找到合并的元素");
return null;
}
System.out.println("两个链表具有相同的尾部节点,则两个链表拥有合并的节点元素");
LinkNode node1 = head1;
LinkNode node2 = head2;
int link1Length = this.calculateLink1Length(head1);
int link2Length = this.calculateLink1Length(head2);
int moveLength = Math.abs(link1Length - link2Length);
if (link1Length > link2Length) {
node1 = head1.moveNext(moveLength);
System.out.println("链表1向后移动" + moveLength + "次,现在的节点为" + node1.getAddress());
} else {
node2 = head2.moveNext(moveLength);
System.out.println("链表2向后移动" + moveLength + "次,现在的节点为" + node2.getAddress());
}
while (node1.hasNext() && node2.hasNext()) {
System.out.println("链表1节点" + node1.getAddress() + "->" + node1.getNext().getAddress());
System.out.println("链表2节点" + node2.getAddress() + "->" + node2.getNext().getAddress());
node1 = node1.getNext();
node2 = node2.getNext();
if (node1.addressSameWith(node2)) {
System.out.println("合并的元素为" + node1.getAddress());
return node1;
}
}
System.out.println("未找到合并的元素");
return null;
}
private int calculateLink1Length(LinkNode head1) {
int linkLength = 1;
LinkNode node = head1;
while (node.hasNext()) {
linkLength++;
node = node.getNext();
}
return linkLength;
}
private LinkNode findNodeLastNode(LinkNode head) {
LinkNode lastNode = head;
while (lastNode.hasNext()) {
lastNode = lastNode.getNext();
}
System.out.println("链表最后一个节点" + lastNode.getAddress());
return lastNode;
}
}

单元测试用例

package com.xianyanyang.linklist.calculator;
import com.xianyanyang.linklist.node.LinkNode;
import junit.framework.TestCase;
public class ConnectiveNodeCalculatorTest extends TestCase {
private LinkNode nodeA;
private LinkNode nodeB;
private LinkNode nodeD;
private LinkNode nodeE;
private LinkNode nodeF;
private LinkNode nodeX;
private LinkNode nodeY;
private LinkNode nodeZ;
@Override
public void setUp() {
nodeA = new LinkNode("A");
nodeB = new LinkNode("B");
nodeD = new LinkNode("D");
nodeE = new LinkNode("E");
nodeF = new LinkNode("F");
nodeX = new LinkNode("X");
nodeY = new LinkNode("Y");
nodeZ = new LinkNode("Z");
}
public void testCalculateConnectiveNode() {
nodeA.setNext(nodeB);
nodeB.setNext(nodeX);
nodeD.setNext(nodeE);
nodeE.setNext(nodeF);
nodeF.setNext(nodeX);
nodeX.setNext(nodeY);
nodeY.setNext(nodeZ);
ConnectiveNodeCalculator connectiveNodeCalculator = new ConnectiveNodeCalculator();
connectiveNodeCalculator.calculateConnectiveNodeV2(nodeA, nodeD);
}
}

运行结果

图3 单元测试用例运行结果

结论

时间复杂度为O(n)

注意点

1、判断两个链表是否有同一个尾部节点元素,如果没有则表示两个链表没有交叉点;

2、如果有同一个尾部节点元素,则将长度较长的链表的头节点向后移动abs(长链表长度-短链表长度),然后同时遍历两个链表,判断是否有相同的交叉节点。

发布于: 2020 年 07 月 24 日 阅读数: 5
用户头像

且听且吟

关注

没有绝世高手 2018.06.30 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营 第八周 课后练习