链表相交 Posted on 2021-07-14 00:00:00 2021-07-14 00:00:00 by Author 摘要 给定两个链表的头指针，你能找到两个链表相交的节点吗？？？？？？？？ # 链表相交 > 写于2021/05/22 1. 题目描述：给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。换句话说，如果一个链表的第k个节点与另一个链表的第j个节点是同一节点（引用完全相同），则这两个链表相交。、 2. 实列描述：、 - 示例一： - 输入：1->2->3->4->5->6 ： 6->3->4->5->6 - 输出：Reference of the node with value = 3 - 实列二： - 输入： 4->1->8->4->5 ：5->0->1->8->4->5 - 输出：Reference of the node with value = 1 3. 解题思路： - 对于该题描述，简单而言就是要找到链表相交的节点，我们知道，如果有链表相交的节点，那么相交节点之后，两个链表后面都是同一段链表。所以首先找到两个链表长度最小的链表，然后对于长度较大的链表，移动到和较小链表长度相同的地方，之后，对于指向两个链表的指针同时移动，直到两个链表指针指向的节点是同一个节点，那么就找到链表相交的地方。 4. 代码实现： ``` java public ListNode getIntersectionNode(ListNode headA, ListNode headB) { //定义两个工作指针 ListNode pointA = headA, pointB = headB; //判断那个链表长度长的标志指针（flag = true,代表headA链表长度长，否则headB链表长度长） boolean flag = true; //定义两个表示长度的变量 int lenA = 0, lenB = 0; //找出链表A的长度 while (pointA != null) { lenA++; pointA = pointA.next; } //找出链表B的长度 while (pointB != null) { lenB++; pointB = pointB.next; } //如果链表A长度长于链表B的长度,flag = true if (lenA >= lenB) { flag = true; } //否则flag = false else { flag = false; } //如果flag = true,说明链表A长度长于链表B的长度，则移动链表A，使其链表A的长度与链表B的长度一样 if (flag) { int len = lenA - lenB; while (len > 0) { headA = headA.next; len--; } } //如果flag = false,说明链表B长度长于链表A的长度，则移动链表B，使其链表A的长度与链表A的长度一样 else { int len = lenB - lenA; while (len > 0) { headB = headB.next; len--; } } //同时移动链表A与链表B,判断指向两个链表的指针是否相同，如果相同，返回相同的节点 while (headA != null && headB != null) { if (headA == headB) { return headA; } headA = headA.next; headB = headB.next; } //如果到最后没有找到相同的节点，就说明没有共同的节点 return null; } ```
{{ item.content }}
{{ child.content }}