架构一期 第八周作业

有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。

请用代码（或伪代码）描述算法，并给出时间复杂度。

public class SingleLinkedList {

private Node head = null;

private Node tail = null;

private int count = 0;

public void addNode(Integer data) {

Node node = new Node(data);

if (head == null) {

head = node;

tail = head;

} else {

tail.next = node;

tail = node;

}

count++;

}

/**

链表反转

*/

public static Node revers(Node head) {

/*

* 定义三个指针： 第一个指针指向当前正在处理的节点；

* 第二个指针指向当前处理节点的下一个节点，该指针是为了保证正常的遍历完顺序链表的所有节点；

* 第三个指针指向当前处理节点的上一个节点，这里主要是为了修改当前指针的指向，也就是指向反向；

*/

Node newHead = null;

Node preNode = null;

Node current = head;

Node nextNode = null;

while (current != null) {

nextNode = current.next;

if (nextNode == null) {

newHead = current;

}

current.next = preNode;

preNode = current;

current = nextNode;

}

return newHead;

}

/**

* 如果两个链表存在合并，那么不难想象这两个链表共同构成了一个 Y 型。

* 因此，只要分别遍历这两个链表，找到尾端节点，判断尾端节点是否相同即可确认是否相交。

* 如果要求这种情况的交点，由于相交部分全部都相同，因此，只需要先得到两个链表的差，

* 用两个指针分别指向这两个链表 P1,P2 假定 P1 与 P2 相差为 N，那么将 P1 移动 N 个节点后， P1 与 P2 同时出发，第一个相等的节点即为交点。

*

* @Description 描述方法用途

* @method getSameNode

* @param head1

* @param head2

* @return Node

* @date Nov 15, 2020 10:24:24 PM

*/

public static Node getSameNode(Node head1, Node head2) {

if (head1 == null || head2 == null)

return null;

Node cur1 = head1;

Node cur2 = head2;

int n = 0;

while (cur1 != null) {

n++;

cur1 = cur1.next;

}

while (cur2 != null) {

n--;

cur2 = cur2.next;

}

//尾节点不同不相交

// if (cur1!=cur2)

//如果大于 0，链表 1 比链表 2 长 n

cur1 = n > 0 ? head1 : head2;

cur2 = cur1 == head1 ? head2 : head1;

n = Math.abs(n);

while (n != 0) {

n--;

cur1 = cur1.next;

}

while (cur1.data != cur2.data) {

cur1 = cur1.next;

cur2 = cur2.next;

}

return cur1;

/*

方法 2，反转链表，不相等的节点的上一个就是相交的节点

* head1 = SingleLinkedList.revers(head1); head2 =

* SingleLinkedList.revers(head2);

*/

}

public static void main(String[] args){

SingleLinkedList linkList1 = new SingleLinkedList();

linkList1.addNode(1);

linkList1.addNode(2);

linkList1.addNode(5);

linkList1.addNode(7);

linkList1.addNode(9);

Node head1 = linkList1.head;

while (head1 != null) {

System.out.println(head1.data);

head1 = head1.next;

}

SingleLinkedList linkList2 = new SingleLinkedList();

linkList2.addNode(4);

linkList2.addNode(5);

linkList2.addNode(7);

linkList2.addNode(9);

Node head2 = linkList2.head;

while (head2 != null) {

System.out.println(head2.data);

head2 = head2.next;

}

Node sameNode = SingleLinkedList.getSameNode(linkList1.head, linkList2.head);

System.out.println("合并的第一个元素是：" + sameNode.data);

// 3.1、如何从链表中删除重复数据

//

// 3.2、如何找出单链表中的倒数第 k 个元素

//

// 3.3、如何实现链表的反转

//

// 3.4、如何从尾到头输出单链表

//

// 3.5、如何寻找单链表的中间结点

//

// 3.6、如何检测一个链表是否有环

//

// 3.7、如何在不知道头结点的情况下删除指定结点

//

// 3.8、如何判断两个链表是否相交

//

}

public Node getHead() {

return head;

}

public void setHead(Node head) {

this.head = head;

}

public Node getTail() {

return tail;

}

public void setTail(Node tail) {

this.tail = tail;

}

public int getCount() {

return count;

}

public void setCount(int count) {

this.count = count;

}

class Node {

Integer data;

Node next;

Node() {

}

Node(Integer data) {

this.data = data;

}

Node(Integer data, Node next) {

this.data = data;

this.next = next;

}

public String toString() {

String res = "";

Node tnode = head;

if (tnode != null) {

StringBuilder lbstr = new StringBuilder(tnode.data.toString());

while (tnode.next != null) {

tnode = tnode.next;

lbstr.append(",").append(tnode.data.toString());

}

res = lbstr.toString();

tnode = null;

lbstr = null;

}

return res;

}

}

}

获取第一个合并的节点的时间复杂度的级别：O(2n).