AcWing 66. 两个链表的第一个公共结点 (2012算法题)

题目：

输入两个链表，找出它们的第一个公共结点。

当不存在公共节点时，返回空节点。

数据范围

链表长度 [1,2000]。

保证两个链表不完全相同，即两链表的头结点不相同。

样例

 给出两个链表如下所示：
 A：        a1 → a2
                    
                      c1 → c2 → c3
                                
 B:     b1 → b2 → b3
 
 输出第一个公共节点c1

算法思想：假设公共部分长度为c，A链非公共部分长度为a，b非公部分长度为b。假设有两个指针p1与p2，p1移动途径为a->c->b（从a开始遍历链表A，结束后再从B的链头开始遍历b。同步的p2移动途径为b->c->a（从b开始遍历链表B，结束后再从A的链头开始遍历a。可以看到两者最后的移动距离都是a+b+c,此时必然会相遇。）

 /**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     struct ListNode *next;
  * };
  */
 struct ListNode *findFirstCommonNode(struct ListNode *headA, struct ListNode *headB) {
     struct ListNode *q,*p;
     q = headB;
     p = headA;
     while (p != q)
     {
         if (p)
         {
             p = (*p).next;
         }
         else{
             p = headB;
         }
         if (q)
         {
             q = (*q).next;
         }
         else{
             q = headA;
         }
     }
     return p;
     
 }

巴特西

AcWing 66. 两个链表的第一个公共结点 (2012算法题)

题目：

数据范围

样例

最新文章

热门文章