leetcode做题笔记160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

思路一：模拟题意

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if(!headA||!headB)return NULL;
    struct ListNode *p = headA,*q = headB;
    while(q!=p){
        q = q ? q->next:headA;
        p = p ? p->next:headB;
    }
    return p;
 
 
 
}

分析：

本题返回相交链表的相交节点，可以利用pq两个指针记录遍历位置，当q==p时即遍历到相交节点，返回即可

总结：

本题考察对链表的利用，利用指针记录位置当两个指针到相交节点返回即可解决