Leetcode 160. Intersection of Two Linked Lists

找出兩個Linked Lists的最早的公共數，c1為最早的公共數

Python

方法一 :

一旦兩個Linked Lists相交，兩者的其餘部分將相同到結束。所以將 l2 附加到 l1 並將 l1 附加到 l2，然後相交的部分 l1l2 和 l2l1 具有相同的長度，並且在兩個Linked Lists的相同位置會有一個相交節點，使其餘部分相交。

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        h1=headA
        h2=headB
        while h1!=h2:
            if not h1:
                h1=headB           #l2 附加到 l1
            else:
                h1=h1.next         #下一位
            if not h2:
                h2=headA           #l1 附加到 l2
            else:
                h2=h2.next         #下一位
        return h1                  #當h1,h2相等時，回傳值

方法二: 棧

因為後面的元素是相等的，所以使用棧把相等元素都彈出來，那麼不等元素就是所求。

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        stack1=[]
        stack2=[]
        while headA:
            stack1.append(headA)        #加入stack
            headA=headA.next
        while headB:
            stack2.append(headB)
            headB=headB.next
        ans=None
        while stack1 and stack2:
        #pop出來，比較值，相等時s1帶入ans
            s1=stack1.pop()             
            s2=stack2.pop()
            if s1!=s2:
                return ans
            else:
                ans=s1
        return ans

C++

此題是求兩個鍊錶的交點。我們可以用兩個指針分別指向兩個鍊錶的頭節點，然後同時遍歷這兩個鍊錶，直到找到第一個相同的節點為止。具體的做法是，如果當前指針不為空，則指向下一個節點；如果當前指針為空，則指向另一個鍊錶的頭節點。這樣一來，兩個指針就會在第一個相同的節點相遇。

時間複雜度：O(m+n)，其中 m 和 n 分別是兩個鍊錶的長度。

空間複雜度：O(1)。

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

Python

C++

相關