写点什么

架构师训练营第一期 - 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); }

}
复制代码


结果



问题 2




用户头像

习习

关注

还未添加个人签名 2018.08.08 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营第一期 - week8