C++怎么求兩個鏈表的交點

這篇文章主要介紹“C++怎么求兩個鏈表的交點”，在日常操作中，相信很多人在C++怎么求兩個鏈表的交點問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”C++怎么求兩個鏈表的交點”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！

求兩個鏈表的交點

這道求兩個鏈表的交點題要求執(zhí)行時間為 O(n)，則不能利用類似冒泡法原理去暴力查找相同點，事實證明如果鏈表很長的話，那樣的方法效率很低。我也想到會不會是像之前刪除重復(fù)元素的題一樣需要用兩個指針來遍歷，可是想了好久也沒想出來怎么弄。無奈上網(wǎng)搜大神們的解法，發(fā)覺其實解法很簡單，因為如果兩個鏈長度相同的話，那么對應(yīng)的一個個比下去就能找到，所以只需要把長鏈表變短即可。具體算法為：分別遍歷兩個鏈表，得到分別對應(yīng)的長度。然后求長度的差值，把較長的那個鏈表向后移動這個差值的個數(shù)，然后一一比較即可。代碼如下： 

C++ 解法一：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (!headA || !headB) return NULL;
        int lenA = getLength(headA), lenB = getLength(headB);
        if (lenA < lenB) {
            for (int i = 0; i < lenB - lenA; ++i) headB = headB->next;
        } else {
            for (int i = 0; i < lenA - lenB; ++i) headA = headA->next;
        }
        while (headA && headB && headA != headB) {
            headA = headA->next;
            headB = headB->next;
        }
        return (headA && headB) ? headA : NULL;
    }
    int getLength(ListNode* head) {
        int cnt = 0;
        while (head) {
            ++cnt;
            head = head->next;
        }
        return cnt;
    }
};

Java 解法一：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        int lenA = getLength(headA), lenB = getLength(headB);
        if (lenA > lenB) {
            for (int i = 0; i < lenA - lenB; ++i) headA = headA.next;
        } else {
            for (int i = 0; i < lenB - lenA; ++i) headB = headB.next;
        }
        while (headA != null && headB != null && headA != headB) {
            headA = headA.next;
            headB = headB.next;
        }
        return (headA != null && headB != null) ? headA : null;
    }
    public int getLength(ListNode head) {
        int cnt = 0;
        while (head != null) {
            ++cnt;
            head = head.next;
        }
        return cnt;
    }
}

這道題還有一種特別巧妙的方法，雖然題目中強(qiáng)調(diào)了鏈表中不存在環(huán)，但是我們可以用環(huán)的思想來做，我們讓兩條鏈表分別從各自的開頭開始往后遍歷，當(dāng)其中一條遍歷到末尾時，我們跳到另一個條鏈表的開頭繼續(xù)遍歷。兩個指針最終會相等，而且只有兩種情況，一種情況是在交點處相遇，另一種情況是在各自的末尾的空節(jié)點處相等。為什么一定會相等呢，因為兩個指針走過的路程相同，是兩個鏈表的長度之和，所以一定會相等。這個思路真的很巧妙，而且更重要的是代碼寫起來特別的簡潔，參見代碼如下：

C++ 解法二：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (!headA || !headB) return NULL;
        ListNode *a = headA, *b = headB;
        while (a != b) {
            a = a ? a->next : headB;
            b = b ? b->next : headA;
        }
        return a;
    }
};

Java 解法二：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode a = headA, b = headB;
        while (a != b) {
            a = (a != null) ? a.next : headB;
            b = (b != null) ? b.next : headA;
        }
        return a;
    }
}

到此，關(guān)于“C++怎么求兩個鏈表的交點”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識，請繼續(xù)關(guān)注億速云網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>