判断两条链表是否相交（公共部分）并找出相交处

爱被打了一巴掌 2022-10-02 15:55 162阅读 0赞

**Problem：**  
　　两个单链表相交的一系列问题  
　　【题目】 在本题中，单链表可能有环，也可能无环。给定两个  
　　　　单链表的头节点 head1和head2，这两个链表可能相交，也可能  
　　　　不相交。请实现一个函数， 如果两个链表相交，请返回相交的  
　　　　第一个节点；如果不相交，返回null 即可。  
　　要求：

如果链表1 的长度为N，链表2的长度为M，时间复杂度请达到 O(N + M)，额外  
　　　　空间复杂度请达到O(1)

**Solution：**  
　　对于判断单链表是否有环，则使用快慢指针即可知道，两指针相交，则有环  
　　对于判断双链表是否相交，则判断遍历链表的最后指针的地址是否相同，相同则有公共部分  
　　然后在从头遍历，长的链表先遍历长的部分，然后一起遍历，当指针相同时，则为相交的部位。

**Code:**

**　　**

1 #include <iostream>
      2 
      3 using namespace std;
      4 
      5 struct Node
      6 {
      7     int val;
      8     Node* next;
      9     Node(int a = 0) :val(a), next(NULL) {}
     10 };
     11 
     12 void FindNode(Node* head1, Node* head2)
     13 {
     14     if (head1->next == NULL || head2->next == NULL)
     15         return;
     16     Node *p1, *p2;
     17     p1 = head1->next;
     18     p2 = head2->next;
     19     int size1, size2;//计算链表长度
     20     size1 = size2 = 1;
     21     while (p1->next || p2->next)
     22     {
     23         if (p1->next)
     24         {
     25             p1 = p1->next;
     26             size1++;            
     27         }
     28         if (p2->next)
     29         {
     30             p2 = p2->next;
     31             size2++;
     32         }
     33     }
     34     if (p1 != p2)
     35     {
     36         cout << "List1 and List2 have no commmon part!" << endl;
     37         return;
     38     }
     39     cout << "List1 and List2 have commmon part!" << endl;
     40     //重新遍历，找到交点
     41     p1 = head1->next;
     42     p2 = head2->next;
     43     for (int i = 0; i<(size1>size2 ? size1 - size2 : size2 - size1); ++i)//长的先遍历
     44     {
     45         if (size1 > size2)
     46             p1 = p1->next;
     47         else
     48             p2 = p2->next;
     49     }
     50     while (p1 != p2)
     51     {
     52         p1 = p1->next;
     53         p2 = p2->next;
     54     }
     55     cout << "相交部位为：addr：" << p1 << "  val:" << p1->val << endl;
     56 
     57 }
     58 
     59 void Test()
     60 {
     61     int a[] = { 1,2,3,4,5,6 };
     62     int b[] = { 4,5,6 };
     63     int c[] = { 7,8,9,10 };
     64     Node* head1 = new Node(-1);
     65     Node* head2 = new Node(-1);
     66     Node* p1 = head1;
     67     Node* p2 = head2;
     68 
     69     for (auto n : a)
     70     {
     71         Node* q = new Node(n);
     72         p1->next = q;
     73         p1 = q;
     74     }
     75     p1->next = NULL;
     76     for (auto n : b)
     77     {
     78         Node* q = new Node(n);
     79         p2->next = q;
     80         p2 = q;
     81     }
     82     p2->next = NULL;
     83 
     84     cout << "相交之前判断：" << endl;
     85     FindNode(head1, head2);
     86     cout << "***********************" << endl;
     87     for (auto n : c)
     88     {
     89         Node* q = new Node(n);
     90         p1->next = q;
     91         p1 = q;
     92         p2->next = q;
     93         p2 = q;
     94     }
     95     p1->next = NULL;
     96     p2->next = NULL;
     97 
     98     cout << "相交之后判断：" << endl;
     99     FindNode(head1, head2);
    100     cout << "***********************" << endl;
    101 }

转载于:https://www.cnblogs.com/zzw1024/p/10989469.html