[Leetcode]160. Intersection of Two Linked Lists(C++)

题目描述

题目链接：160. Intersection of Two Linked Lists

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

例子

见官网示例。

Follow Up

Note

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.

Each value on each linked list is in the range [1, 10^9].

Your code should preferably run in O(n) time and use only O(1) memory.

解题思路

如果两个链表长度一样的话很简单，只需要一次遍历逐个比较节点是否相同即可，发现第一个节点相同时就返回该节点。但是链表长度不一样，因此我们可以先遍历一次获得两个链表的长度，再计算其长度差 n，再在较长的链表先遍历 n 步，然后再逐个节点比较即可。

代码如下：

/**
 * 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) {
        if (!headA || !headB) {
            return nullptr;
        }
        
        int lenA = 0;
        int lenB = 0;
        ListNode *currA = headA;
        ListNode *currB = headB;

        // 计算长度
        while (currA) {
            lenA++;
            currA = currA->next;
        }
        while (currB) {
            lenB++;
            currB = currB->next;
        }

        currA = headA;
        currB = headB;
        while (currA && currB) {
            // A B 遍历的节点先同步位置
            if (lenA > lenB) {
                currA = currA->next;
                lenA--;
            } else if (lenB > lenA) {
                currB = currB->next;
                lenB--;
            }
            else {
                // 比较 A B 节点是否相同
                if (currA == currB) {
                    return currA;
                }
                currA = currA->next;
                currB = currB->next;
            }
        }

        return currA;

时间复杂度: O(n)
空间复杂度: O(1)

GitHub 代码同步地址： 160.IntersectionOfTwoLinkedLists.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions