數據結構鏈表

-1

我被要求解決這個問題：數據結構鏈表

有兩個單獨鏈接列表。我需要編寫一個方法來獲取這兩個鏈表，並返回一個指向這兩個鏈表中後綴相同的起點的指針。

實施例：

給出：

1->2->4->6->8->10->15 
2->4->8->10->15

返回值將是一個指向構件 - 8.

但是，我需要做的是在不改變列表或使用更多的內存，和 - 我們需要掃描列表只有一次，意味着T(n)=O(n)。

來源

2017-07-05 Roi Zrihan

這肯定看起來像一個家庭作業的問題。堆棧溢出不會爲你做功課。寫一些代碼，試着讓它工作，然後當你遇到特定問題時尋求幫助。 – AlienHoboken

你在編寫什麼編程語言？ – Yonlif

列表是否保證排序？ – wildplasser

措施兩份名單的長度
快進在較長的列表中，直到它們是相同的長度
向前步行通過步驟兩個列表，並記住節點的最後一個點之後，其中的列表有不同的元素。這些是你可以返回的指針。

現在......我知道你說你只需要掃描列表一次，我做了兩次，但你也表示，這意味着T（N）= O（N），那就是不是是正確的。

掃描列表兩次是也在爲O（n）和需要解決的問題，而無需使用額外的無界存儲器。

來源

2017-07-06 03:52:37

這將需要*至少兩次通過列表。 – wildplasser

@wildpasser如上所述，它只需要兩遍 - 每個列表需要一遍才能進行測量，並且在（2）和（3）中的每個項目上只有一步。 –

這是一個僞代碼..不Python代碼爲此事採取兩個列表，並讓P1點長列表和P2點短名單，

while p1->next!=NULL: 
    if p1->value = p2->value: 
     p1 = p1->next 
     p2 = p2->next 
    else: 
     p1 = p1->next 
     returnpointer = p1->next// if it happens that some elements are same towards end but not the last element.. p1->next would be pointing to NULL anyways and else.. it'll always be the element next to the last element which wasn't same 
return returnpointer

來源

2017-07-06 07:26:44

數據結構鏈表

回答

相關問題