(转)Intersection-of-Two-Linked-Lists - (sunznx) 振翅飞翔
19 February 2018
原文: LeetCode 160 Intersection of Two Linked Lists(链表相交)

介绍

leetcode 160 Intersection of Two Linked Lists

写一个程序来找出两个单链表相交的开始处。

例如,如下有两个链表

分析

代码

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == NULL || headB == NULL) {
            return NULL;
        }

        ListNode *n1 = headA;
        ListNode *n2 = headB;

        bool switched = false;

        while (n1 != NULL && n2 != NULL) {
            if (n1 == n2) {
                return n1;
            }

            n1 = n1->next;
            n2 = n2->next;

            if (n1 == NULL && n2 == NULL && switched == true) {
                return NULL;
            }

            if (n1 == NULL) {
                n1 = headB;
                switched = true;
            }
            if (n2 == NULL) {
                n2 = headA;
                switched = true;
            }
        }

        return NULL;
    }
};