Java 中查找两个链表的交点

链表是一种线性数据结构，其中每个节点有两个块，一个块包含节点的值或数据，另一个块包含下一个节点的地址。

假设我们有一个链表，每个节点包含一个随机指针，该指针指向列表中的其他节点。任务是找到两个链表相互交叉的节点。如果它们不相交，则返回 NULL 或空作为输出。

例如

输入 1

输出

2

说明：由于给定的链表在值为“2”的节点处相交，因此我们将返回“2”作为输出。

输入 2

输出

NULL

说明：由于没有公共点，因此在这种情况下我们将返回 NULL。

解决此问题的方法

我们有两个链表，它们在某个公共点处相交。为了找到交点，我们将遍历两个链表，直到我们发现它们都指向相同的值。在某个点，链表的下一个节点的指针将相同。因此，我们将返回该点的值。

• 使用两个链表，分别包含数据和指向下一个节点的指针。
• 函数 commonPoint(listnode*headA, listnode*headB) 分别接受两个链表指针，并返回链表的公共点或交点的值。
• 一个查找链表长度的整型函数将返回从列表头部开始的两个链表的长度。
• 现在创建一个指向两个列表头的指针，并遍历长度较长的列表，直到 (第一个列表的长度 - 第二个列表的长度)。
• 现在遍历列表，直到我们找到下一个指针相等。
• 返回两个列表相交的特定节点的值。

示例

在线演示

public class Solution {
   static listnode headA,
   headB;
   static class listnode {
      int data;
      listnode next;
      listnode(int d) {
         data = d;
         next = null;
      }
   }
   int count(listnode head) {
      int c = 0;
      while (head != null) {
         c++;
         head = head.next;
      }
      return c;
   }
   int commonPoint(listnode headA, listnode headB) {
      listnode p1 = headA;
      listnode p2 = headB;
      int c1 = count(headA);
      int c2 = count(headB);
      if (c1 > c2) {
         for (int i = 0; i < c1 - c2; i++) {
            if (p1 == null) {
               return - 1;
            }
            p1 = p1.next;
         }
      }
      if (c1 < c2) {
         for (int i = 0; i < c2 - c1; i++) {
            if (p2 == null) {
               return - 1;
            }
            p2 = p2.next;
         }
      }
      while (p1 != null &amp;&amp; p2 != null) {
         if (p1.data == p2.data) {
            return p1.data;
         }
         p1 = p1.next;
         p2 = p2.next;
      }
      return - 1;
   }
   public static void main(String[] args) {
      Solution list = new Solution();
      list.headA = new listnode(5);
      list.headA.next = new listnode(4);
      list.headA.next.next = new listnode(9);
      list.headA.next.next.next = new listnode(7);
      list.headA.next.next.next.next = new listnode(1);
      list.headB = new listnode(6);
      list.headB.next = new listnode(7);
      list.headB.next.next = new listnode(1);
      System.out.println(list.commonPoint(headA, headB));
   }
}

运行以上代码将生成以下输出：

输出

7

说明：给定的链表在 7 处相交。

Dev Prakash Sharma

更新于： 2021-02-23

547 次浏览

开启你的 职业生涯

完成课程获得认证

开始学习