LeetCode 160. Intersection of Two Linked Lists (Easy)

两个链表，可能会有交叉，返回交叉点的元素，若没有交叉则返回null。

原始问题

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:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

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.

解题思路

若将b1节点连接到c3节点后面，此问题就转换为了LeetCode 142. Linked List Cycle II问题，可用相同方法求解，最后断开c3 -> b1的连接即可。LeetCode题解中就是这样做的，不过对此还可以进行优化。

开始时直接设置slow及fast指针进行移动，fast指针在移动过程中会遇到null，对此进行处理即可。第一次遇到null时进行连接，若第二次遇到null则说明两个链表没有交叉。其余步骤与LeetCode 142中的做法完全一样，具体见代码。

AC代码

C语言

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode * slow, * fast, *p, *tail;
    
    if (!headA || !headB) {
        return NULL;
    }
    
    slow = headA;
    fast = headA;
    p = headA;
    tail = NULL;
    
    do{
        if (!fast->next) {
            if (tail) {
                tail->next = NULL;
                return NULL;
            }
            fast->next = headB;
            tail = fast;
        }
        if (!fast->next->next) {
            if (tail) {
                tail->next = NULL;
                return NULL;
            }
            fast->next->next = headB;
            tail = fast->next;
        }
        
        slow = slow->next;
        fast = fast->next->next;
    }while(slow != fast);
    
    while (p != slow) {
        p = p->next;
        slow = slow->next;
    }
    
    tail->next = NULL;
    
    return p;
}

相关题目

LeetCode 141. Linked List Cycle (Easy)
LeetCode 142. Linked List Cycle II (Medium)