Leetcode题解 剑指 Offer 52. 两个链表的第一个公共节点

PROBLEM

剑指 Offer 52. 两个链表的第一个公共节点

难度 简单

MY ANSWER

先遍历一遍得到链表的长度，然后长的先走差值，再一起走比较节点地址是否相等。时间复杂度O(m+n)，空间复杂度O(1)。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int alen = 0, blen = 0;
        ListNode* tmp = headA;
        while(tmp) {
            tmp = tmp->next;
            alen++;
        }
        tmp = headB;
        while(tmp) {
            tmp = tmp->next;
            blen++;
        }
        int before = alen - blen;
        ListNode* tmpa = headA;
        ListNode* tmpb = headB;
        if(before > 0) {
            while(before--) {
                tmpa = tmpa->next;
            }
        }
        else if(before < 0){
            before = -before;
            while(before--) {
                tmpb = tmpb->next;
            }
        }
        while(tmpa) {
            if(tmpa == tmpb) {
                return tmpa;
            }
            tmpa = tmpa->next;
            tmpb = tmpb->next;
        }
        return nullptr;
    }
};

BETTER SOLUTION

思路相同，代码可以简化为一起走，走到末尾就从另一个头节点开始走，这样两个指针会在相交处相遇，因为一个走了l1+skip2，一个走了l2+skip1，l1-l2=skip1-skip2，所以这两个相等。时间空间复杂度相同。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == nullptr || headB == nullptr) {
            return nullptr;
        }
        ListNode *pA = headA, *pB = headB;
        while (pA != pB) {
            pA = pA == nullptr ? headB : pA->next;
            pB = pB == nullptr ? headA : pB->next;
        }
        return pA;
    }
};

SUMMARY

理解简化的代码的思路。