[C语言][剑指offer篇]--两个链表的第一个公共节点

题目描述

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

理清思路 双指针

• 定义ptrA指向headA，ptrB指向headB。
  

  
  

• 首先判断特殊情况，只要其中一个链表为空，则永远不会相交，返回NULL。
  

  
  

• 分别遍历链表，当ptrA走到尾时，指向headB，同时ptrB走到尾时，指向headA。
  

  
  

  只有当ptrA 等于 ptrB时才退出循环，返回ptrA。
  

  
  

代码实现 双指针

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {

    struct ListNode *ptrA = headA;
    struct ListNode *ptrB = headB;
    
    if(headA == NULL || headB == NULL)
    {
        return NULL;
    }

    while(ptrA != ptrB)
    {
        ptrA = ptrA ? ptrA->next:headB;
        ptrB = ptrB ? ptrB->next:headA;
    }

    return ptrA;
}

 有没有人考虑过这段代码会陷入死循环？实际上，这段代码不会陷入死循环，即使输入两条没有交点的链表，最后也会因为 NULL = NULL而退出循环，并且返回NULL。