算法基础之打印相交链表的公共节点

aaron-han

不考虑带环的情况...
这里面其实包含了两个问题：判断链表相交和找两个相交链表的第一个公共点。
思路：首先需要理解的是若两个链表相交，则一定是呈Y型。所以我们分别遍历两个链表，找到最后一个节点，若它们相同，则一定相交。然后我们从后往前考虑，假设两个链表有n个公共节点，两个链表的长分别为l和m(设l>m)，那么我们先让较长的链表遍历l-m个。两个链表剩余部分长度是相等的(m)，则同步遍历比较，若相同，则输出。
import com.linkedlist.LinkedListReverse.Node;/** * 打印相交链表的公共节点 *  * @author aaron-han *  */public class LinkedListCommonNodes {public static void main(String[] args) {Node a = new Node("NodeA");Node b = new Node("NodeB");Node c = new Node("NodeC");Node d = new Node("NodeD");Node e = new Node("NodeE");Node f = new Node("NodeF");Node g = new Node("NodeG");Node h = new Node("NodeH");// a->f->g->ha.next = f;f.next = g;g.next = h;// b->c->d->e->f->g->hb.next = c;c.next = d;d.next = e;e.next = f;f.next = g;g.next = h;System.out.println(isIntersected(a, c));printCommonNode(a, c);}// 判断是否相交public static boolean isIntersected(Node a, Node b) {Node headA = a;Node headB = b;while (headA.next != null) {headA = headA.next;}while (headB.next != null) {headB = headB.next;}if (headA == headB) {return true;}return false;}// 打印公共节点public static void printCommonNode(Node a, Node b) {int lengthA = getListLength(a);int lengthB = getListLength(b);Node longerList = a;Node shorterList = b;int lengthDiff = lengthA - lengthB;if (lengthDiff < 0) {longerList = b;shorterList = a;lengthDiff = lengthB - lengthA;}// 使较长的链表先遍历lengthDiff个for (int i = 0; i < lengthDiff; i++) {longerList = longerList.next;}// 此时等长，同步遍历while (longerList != null && shorterList != null) {if (longerList == shorterList) {System.out.println(longerList.name);}longerList = longerList.next;shorterList = shorterList.next;}}public static int getListLength(Node node) {int length = 0;if (node == null) {return length;}while (node != null) {node = node.next;length++;}return length;}}