思考：
有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
请用代码（或伪代码）描述算法，并给出时间复杂度。
为了解答这个问题，以 Java 语言为例。
问题的思考出发点，首先在于单向链表的结构设计，为了简化理解，链表的节点存储的数据类型为基本数据类型，即整数。节点代码如下：
class Node{ private int val; private Node next; public Node(int val){ this.val = val; }
public int getVal() { return val; }
public void setVal(int val) { this.val = val; }
public Node getNext() { return next; }
public void setNext(Node next) { this.next = next; } }
复制代码
基于节点，链表的结构在于存储头节点即可，故链表结构的代码如下：
package net.mingsoft.test;
import java.util.HashMap;import java.util.Map;
class MyLinkedList {
private Node head;
public MyLinkedList(){ }
class Node{ private int val; private Node next; public Node(int val){ this.val = val; }
public int getVal() { return val; }
public void setVal(int val) { this.val = val; }
public Node getNext() { return next; }
public void setNext(Node next) { this.next = next; } }
public Node getHead() { return head; }
public void setHead(Node head) { this.head = head; }
}
复制代码
要进行链表操作，就需要具备链表的增加函数，实现代码如下：
public boolean add(int val){
Node node = new Node(val); // 为了简化理解，不进行并发处理判断 if(head == null){ head = node; return true; } // 递归方法调用 return addNode(head,node);
}
private boolean addNode(Node head, Node node){ if (head == null || node == null){ return false; } else if(head.next == null){ head.next = node; return true; } return addNode(head.next,node);}
复制代码
为了能够针对链表展示，增加遍历的函数，实现代码如下：
public void printLinkedList(){ if(head == null){ System.out.println("Linked List is empty"); } printNode(head);}
private void printNode(Node head){ if(head != null){ System.out.print(head.val + " -> "); if(head.next != null){ printNode(head.next); }else { System.out.print("null"); } }}
复制代码
基于以上基本操作，链表构建成功，接下来探讨如何判断两个链表是否合并。根据问题，实际上能够得出一个结论，那便是两个单向链表一旦合并，则肯定会直接到尾部，不会出现合并一部分然后又分叉的情况。
假设链表 A 的长度为 a + c ，链表 B 的长度为 b + c ，其中 c 为合并部分长度，两个链表的长度关系可以表示为 a + c + b = b + c + a 。
这是两个指针，一个指针从链表 A 的开头开始遍历，当到达链表 A 的尾部时，再从链表 B 的开头开始遍历链表 B，同理，一个指针从链表 B 的开头开始遍历，当到达链表 B 的尾部时，再从链表 A 的开头开始遍历链表 A，不断循环操作，如果链表 A 和 B 具有公共相同的部分，则指针指向的节点一定相同。
这就如同龟兔赛跑，都是在不断跑圈，虽然一开始不相交，但跑步方向相同，跑步的路径相同，两者最终一定相遇。
当链表 A 和 B 不存在合并部分，a + c + b = b + c + a 变为 a + b = b + a，此时，两个指针最终都指向了 null。
因此，基于这个方案，时间复杂度为 O(n)，空间复杂度为 O(1)。
判断链表合并的代码如下：
public Integer getInterSection(MyLinkedList list1, MyLinkedList list2) { if (list1 == null || list2 == null) return null; Node n1 = list1.getHead(),n2 = list2.getHead(); while (n1 != n2) { n1 = (n1 == null) ? list2.getHead() : n1.getNext(); n2 = (n2 == null) ? list1.getHead() : n2.getNext(); } return n1.getVal();}
复制代码
评论