編寫函數以獲取兩個鍊錶的交點  


難度級別 容易獎學金
經常問 ol石 亞馬遜 事實集 高盛 我的旅行 空氣質量 Microsoft微軟 高通公司 Snapdeal 簽證 佐珀
鍊錶

問題陳述  

問題“編寫函數以獲取兩個鍊錶的交點”指出您有兩個鍊錶。 但是它們不是獨立的鍊錶。 它們在某些時候連接在一起。 現在,您需要找到這兩個列表的交點。

例  

編寫函數以獲取兩個鍊錶的交點

1 -> 2
      \
        5 -> 6
      /
3 -> 4
Point of intersection: 5

說明:輸入中顯示了兩個鏈接列表,分別為1、2、5、6和3、4、5、6。它們都在值5的節點處合併。因此輸出為5。

途徑  

這個問題很容易描述。 那裡有兩個 鍊錶 但是它們在某些時候是連接或互連的。 在連接點之前,兩個鍊錶都有不同的節點,在連接節點之後。 它們由單個列表表示。 因此,問題在於我們如何找到這樣的節點(或點)? 該問題可能有許多可能的答案/解決方案。 但是最簡單的方法是找到鍊錶的長度。 只要解決方案簡單,效率就不足以超過時間限制。 但這不是事實。 該解決方案既高效又簡單。

解釋

在此解決方案中,我們將找到兩個鍊錶的長度。 然後,我們將較長鏈接列表的開頭向前移動(倫娜 - )節點。 這裡 倫娜 分別表示鏈接列表A和B的長度。 但是為什麼我們要這樣做呢?

也可以看看
將數字轉換為十六進制Leetcode解決方案

考慮公共鍊錶的長度為z,較長鍊錶的長度為 x + z 而較短鍊錶的是 y + z。 所以直到現在,我們已經搬走了 lenA – lenB 在更長的鍊錶上。 那是 (x + z –(y + z)) = x – y。 這意味著我們已經移到更長的鍊錶上,直到我們當前所在的節點也有長度 y 從加入節點開始,就像較短鍊錶的首部一樣。 然後,我們在兩個鍊錶上同時移動,並檢查兩個當前節點是否相等。 如果是這樣,我們已經找到了交點。 但是,如果我們在鏈接列表的末尾找不到任何這樣的點。 然後,這表明它們沒有交點。

因此,這就是我們編寫函數以獲取兩個鏈接列表的交點的方式。

推薦碼  

C ++代碼查找兩個鏈接列表的交集

#include <bits/stdc++.h>
using namespace std;

struct ListNode{
  int data;
  ListNode *next;
};

ListNode* create(int data){
  ListNode* tmp = new ListNode();
  tmp->data = data;
  tmp->next = NULL;
  return tmp;
}

int length(ListNode *tmp){
    int cnt =  0;
    while(tmp != NULL){
        cnt++;
        tmp = tmp->next;
    }
    return cnt;
}

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    int lenA = length(headA);
    int lenB = length(headB);
    
    if(lenA > lenB){
        int cnt = lenA - lenB;
        while(cnt--)
            headA = headA->next;
    } else {
        int cnt = lenB - lenA;
        while(cnt--)
            headB = headB->next;
    }
    while(headA != NULL && headB != NULL){
        if(headA == headB)
            return headA;
        headA = headA->next;
        headB = headB->next;
    }
    return NULL;
}

int main(){
  ListNode *headA = create(1);
  headA->next = create(2);
  ListNode *headB = create(3);
  headB->next = create(4);
  headA->next->next = headB->next->next = create(5);
  headA->next->next->next = headB->next->next->next = create(6);

  cout<<"Intersection at node: ";
  cout<<getIntersectionNode(headA, headB)->data<<endl;
}
Intersection at node: 5

Java代碼查找兩個鏈接列表的交集

import java.util.*;
class ListNode{
  int data;
  ListNode next;
}

class Main{

    static ListNode create(int data){
        ListNode tmp = new ListNode();
        tmp.data = data;
        tmp.next = null;
        return tmp;
    }

    static int length(ListNode tmp){
        int cnt =  0;
        while(tmp != null){
            cnt++;
            tmp = tmp.next;
        }
        return cnt;
    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = length(headA);
        int lenB = length(headB);

        if(lenA > lenB){
            int cnt = lenA - lenB;
            while(cnt-- > 0)
                headA = headA.next;
        } else {
            int cnt = lenB - lenA;
            while(cnt-- > 0)
                headB = headB.next;
        }
        while(headA != null && headB != null){
            if(headA == headB)
                return headA;
            headA = headA.next;
            headB = headB.next;
        }
        return null;        
    }

    public static void main(String[] args){
    	ListNode headA = create(1);
    headA.next = create(2);
    ListNode headB = create(3);
    headB.next = create(4);
    headA.next.next = headB.next.next = create(5);
    headA.next.next.next = headB.next.next.next = create(6);

    System.out.print("Intersection at node: ");
    System.out.print(getIntersectionNode(headA, headB).data);
  }
}
Intersection at node: 5

複雜度分析  

時間複雜度

上), 因為我們只對鏈接列表中的每個節點運行了一次。 如果存在交叉點,則在到達該節點時將其返回。 否則,每個節點僅被遍歷一次。 這證明了時間複雜度是線性的。

也可以看看
鍊錶週期

空間複雜度

O(1), 我們存儲的唯一內容是鍊錶的長度,這使得該算法僅佔用恆定空間。