LeetCode: 160. Intersection of Two Linked Lists

156 – 159 的题目要收费，(@ ^ @)。。。

题目描述

Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3
begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

题目大意： 找出链条链表相交的节点。

解题思路

如果两条链表相交， 相交点到链表结尾的距离一定的。因此，我们需要将长链表从相距结尾节点短链表长度的节点开始，短链表从头节点开始，依次遍历整个链表。遇到的第一个相等节点 就是相交节点。如果没有遇到，则不存在相交节点。

如，题目例子中的 A 链表从 a1 节点开始遍历， B 链表从 b2 节点开始遍历。 a1 节点不等于 b2 节点，分别步进两个链表。A 链到达 a2 节点， B 链到达 b3 节点，依然不等，继续遍历。此时 A 链到达 c1 节点， B 链也到达 c1 链表，两个节点相等，它就是 A 链和 B 的交点。

AC 代码

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
    int lengthOf(ListNode* head)
    {
        if(head == nullptr) return 0;
        else return lengthOf(head->next) + 1; 
    }
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // 统计 A 链和 B 链的长度
        int lenA = lengthOf(headA);
        int lenB = lengthOf(headB);

        // 长的链表先走 |lenA - lenB| 的步数
        while(lenA > lenB && headA != nullptr)
        {
            --lenA;
            headA = headA->next;
        }
        while(lenB > lenA && headB != nullptr)
        {
            --lenB;
            headB = headB->next;
        }

        // 共同步进，直到遇到相等节点
        ListNode* intersection = nullptr;
        while(headA != nullptr && headB != nullptr)
        {
            if(headA == headB)
            {
                intersection = headA;
                break;
            }

            headA = headA->next;
            headB = headB->next;
        }

        return intersection;
    }
};