架构师训练营第一期 - week8

习习

关注

发布于: 2020 年 11 月 09 日

问题 1

分析

如果有合并，则从第一个合并元素开始都是重合的，尾元素必定是重合的。可以从将两个链表元素放入两个栈结构中，利用先进后出的特性从尾元素开始往前推

Node 类

public class Node {    public String value;    public Node next;
    public Node(String value) {        this.value = value;    }}

复制代码

查找函数

private static Node findFirstCommonNode(Node pHead1, Node pHead2) {
        if (pHead1 == null || pHead2 == null) {            return null;        }        Deque<Node> pStack1 = new ArrayDeque<>();        Deque<Node> pStack2 = new ArrayDeque<>();        // 将元素存入栈中        System.out.println("第一个链表元素为: ");        while (pHead1 != null) {            pStack1.push(pHead1);            System.out.print(pHead1.value + " ");            pHead1 = pHead1.next;        }
        System.out.println("\n第二个链表元素为: ");        while (pHead2 != null) {            pStack2.push(pHead2);            System.out.print(pHead2.value + " ");            pHead2 = pHead2.next;        }
        // 从后往前查找第一个合并元素        Node temp = null;        while (!pStack1.isEmpty() && !pStack2.isEmpty()) {            Node pH1 = pStack1.pop();            Node pH2 = pStack2.pop();            if (pH1.value.equals(pH2.value)) {                temp = pH1;            } else {                break;            }        }        return temp;    }

复制代码

测试

public static void main(String[] args) {
        Node a = new Node("a");        Node b = new Node("b");        Node d = new Node("d");        Node e = new Node("e");        Node f = new Node("f");        Node x = new Node("x");        Node y = new Node("y");        Node z = new Node("z");
        a.next = b;        d.next = e;        e.next = f;        b.next = x;        f.next = x;        x.next = y;        y.next = z;
        Node firstCommonNode = findFirstCommonNode(a, d);        if (firstCommonNode == null) {            System.out.println("\n两个链表不合并");        } else {            System.out.println("\n第一个合并的元素为 " + firstCommonNode.value);        }

    }