Dev - jw

相交链表

题目 - Intersection Of Two Linked Lists

LeetCode-160

两个链表的第一个公共节点

链表相交

难度：简单

分析

双指针法

如果两个链表相交，那么相交点之后的长度是相同的

我们需要做的事情是，让两个链表从同距离末尾同等距离的位置开始遍历。这个位置只能是较短链表的头结点位置。 为此，我们必须消除两个链表的长度差

  1. 指针 pA 指向 A 链表，指针 pB 指向 B 链表，依次往后遍历
  2. 如果 pA 到了末尾，则 pA = headB 继续遍历
  3. 如果 pB 到了末尾，则 pB = headA 继续遍历
  4. 比较长的链表指针指向较短链表head时，长度差就消除了
  5. 如此，只需要将最短链表遍历两次即可找到位置

代码

func getIntersectionNode(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? {
    
    var pa = headA, pb = headB
    
    while pa !== pb {
        pa = pa == nil ? headB : pa!.next
        pb = pb == nil ? headA : pb!.next
    }
    return pa
}

C++

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *pa = headA, *pb = headB;
    
        while (pa != pb) {
            pa = pa == NULL ? headB : pa->next;
            pb = pb == NULL ? headA : pb->next;
        }
        return pa;
    }
};