相交链表求节点

相交链表求节点是一个常见的链表问题，涉及到判断两个链表是否相交以及找到相交部分的节点。本文将从链表的常见问题、判定相交链表、求解相交节点三个方面进行详细阐述。

一、链表的常见问题

链表是一种常见的数据结构，其主要特点是通过指针相连的节点的集合。在链表的操作中，常见的操作包括：插入节点、删除节点、查找节点等。其中，判断链表是否相交是一个重要的问题。

二、判定相交链表

判断两个链表是否相交的常见方法是先遍历两个链表，分别得到它们的长度l1和l2，然后让较长的链表先走|l1-l2|步，使得两个链表起点对齐，最后同时遍历两个链表，找到第一个相同的节点即为相交节点。

/**
 * 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) {
        int lenA = 0, lenB = 0;
        ListNode *p1 = headA, *p2 = headB;
        while (p1 != NULL) {
            lenA++;
            p1 = p1->next;
        }
        while (p2 != NULL) {
            lenB++;
            p2 = p2->next;
        }
        p1 = headA;
        p2 = headB;
        int diff = abs(lenA - lenB);
        if (lenA > lenB) {
            for (int i = 0; i < diff; i++) {
                p1 = p1->next;
            }
        } else {
            for (int i = 0; i < diff; i++) {
                p2 = p2->next;
            }
        }
        while (p1 != NULL && p2 != NULL) {
            if (p1 == p2) {
                return p1;
            }
            p1 = p1->next;
            p2 = p2->next;
        }
        return NULL;
    }
};

三、求解相交节点

找到相交节点后，可以使用双指针法遍历两个链表，直到找到相同节点即为相交节点。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lenA = 0, lenB = 0;
        ListNode *p1 = headA, *p2 = headB;
        while (p1 != NULL) {
            lenA++;
            p1 = p1->next;
        }
        while (p2 != NULL) {
            lenB++;
            p2 = p2->next;
        }
        p1 = headA;
        p2 = headB;
        int diff = abs(lenA - lenB);
        if (lenA > lenB) {
            for (int i = 0; i < diff; i++) {
                p1 = p1->next;
            }
        } else {
            for (int i = 0; i < diff; i++) {
                p2 = p2->next;
            }
        }
        while (p1 != NULL && p2 != NULL) {
            if (p1 == p2) {
                return p1;
            }
            p1 = p1->next;
            p2 = p2->next;
        }
        return NULL;
    }
};

四、总结

本文从链表的常见问题、判定相交链表、求解相交节点三个方面对相交链表求节点问题进行了详细阐述。希望能对读者有所帮助。