LeetCode 160 最简单零内存损耗算法不知道错在哪里

mathGenius

/**
 * 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) {


        while (headA && headB) {
            if (headA->val != headB->val) headB = headB->next;
            else return headA;
            if (headB && headB->val != headA->val) headA = headA->next;
            else return headA;

        }

        return nullptr;


    }
};

//Above is the first method with zero memory needed!
//Below is the second method, I do not why the first method cannot pass all the cases! but the second method can.

/**
 * 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) {

        unordered_set<ListNode*> Set;
        while (headA) {
            Set.insert(headA);
            headA = headA->next;
        }

        while (headB) {
            if (Set.find(headB) != Set.end()) return headB;
            headB = headB->next;
        }

        return nullptr;
    }
};

qtmuniao

mathGenius 第一个算法没太看懂？能解释一下吗？
我之前使用的是一个需要跑三遍，但不需要额外内存的算法：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int a = count(headA), b = count(headB);
        ListNode *itA = headA, *itB = headB;
        while (a > b) {
            --a;
            itA = itA->next;
        }
        
        while (b > a) {
            --b;
            itB = itB->next;
        }
        
        while (itA && itB) {
            if (itA == itB) return itA;
            itA = itA->next;
            itB = itB->next;
        }
        
        return NULL;
    }
    
    int count(ListNode* h) {
        int cnt = 0;
        while (h) {
            ++cnt;
            h = h->next;
        }
        return cnt;
    }
};

mathGenius

qtmuniao 我的第一个算法是逐个比较，如果不重合，直接下一个，“相互”淘汰的方式！

qtmuniao

mathGenius 这种算法不太对，在两个链表等长的时候还行，不等长的时候不对。
另外一种最多两遍的解法可以参考：https://leetcode.com/problems/intersection-of-two-linked-lists/solutions/49785/java-solution-without-knowing-the-difference-in-len/

基本思路是：

双指针
一遍完成后交换

如果链表 A 长为 a，B 长为 b。则 a + b = b + a，一定等长，各种 case 情况可以看上述链接的讨论。

mathGenius

qtmuniao 这个思路和我的有异曲同工。