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

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);
    }
}