leetcode | Intersection of Two Linked Lists

Intersection of Two Linked Lists : https://leetcode.com/problems/intersection-of-two-linked-lists/

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

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.

解析：
我们从例程中可以看出，如果两个链表中的所有节点两两对比，则时间复杂度$O(n^2)$
如果在两个链表相遇之前的两个链表长度如果是相等的，那么，我们只需上下比较2个链表的对应元素，即可找到是否存在的交叉点。因此，可以首先统计2个链表的长度lenA, lenB，让长度更长的链表先走，如A更长，则A先走(lenA-lenB)步，然后A,B一块走，同时比较A,B对应的节点是否相同。时间复杂度O(m+n)=O(n)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

 //Intersection 交叉点，注意O(n)可以遍历链表多次
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == NULL || headB == NULL)
            return NULL;
        int lenA = getListLen(headA);
        int lenB = getListLen(headB);
        if (lenA > lenB) {
            while (lenA != lenB) {
                headA = headA->next;
                lenA--;
            }
        } else {
            while (lenA != lenB) {
                headB = headB->next;
                lenB--;
            }
        }
        while (headA != headB) {
            headA = headA->next;
            headB = headB->next;
        }
        return headA;
    }
private:
    int getListLen(ListNode* head) {
        int len = 0;
        while (head) {
            len++;
            head = head->next;
        }
        return len;
    }
};