相交鏈表求節點

相交鏈表求節點是一個常見的鏈表問題，涉及到判斷兩個鏈表是否相交以及找到相交部分的節點。本文將從鏈表的常見問題、判定相交鏈表、求解相交節點三個方面進行詳細闡述。

一、鏈表的常見問題

鏈表是一種常見的數據結構，其主要特點是通過指針相連的節點的集合。在鏈表的操作中，常見的操作包括：插入節點、刪除節點、查找節點等。其中，判斷鏈表是否相交是一個重要的問題。

二、判定相交鏈表

判斷兩個鏈表是否相交的常見方法是先遍歷兩個鏈表，分別得到它們的長度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;
    }
};

四、總結

本文從鏈表的常見問題、判定相交鏈表、求解相交節點三個方面對相交鏈表求節點問題進行了詳細闡述。希望能對讀者有所幫助。