了解問題 (Understand the Problem)

We are given two singly linked lists and we have to find the point at which they merge.

我們給了兩個單鏈表，我們必須找到它們合并的點。

[SLL 1] 1--->3--->5
                     \
                      9--->12--->17--->None
                     /
     [SLL 2] 7--->8

The diagram above illustrates that the merge occurs at node 9.

上圖說明了合并發生在節點9上。

We can rest assured that the parameters we are given, head1 and head2, which are the heads of both lists will never be equal and will never be none. The two lists are also guaranteed to merge at some point.

我們可以放心，我們給定的參數head1和head2都是兩個列表的頭部，它們永遠不會相等，也永遠不會相等。 這兩個列表也一定會合并。

We need a plan to find and return the integer data value of the node where the two lists merge.

我們需要一個計劃來查找并返回兩個列表合并的節點的整數數據值。

計劃 (Plan)

In order to traverse through the lists to find the point at which they merge, we need to set two different pointers. One for the first singly linked list, another for the second. Remember that we are given the heads of both as parameters, so we will set our pointers to them in order to start from the beginning of each.

為了遍歷列表以查找它們合并的點，我們需要設置兩個不同的指針。 一個用于第一個單鏈表，另一個用于第二個鏈表。 請記住，我們將兩個的頭都作為參數，因此我們將設置指向它們的指針，以便從每個頭開始。

pointer1 = head1
pointer2 = head2

To begin traversing the lists, we’ll need create a while loop to loop through the lists while the lists are not None.

要開始遍歷列表，我們需要創建一個while循環來遍歷列表，而列表不是None。

while not None:

If at any point, pointer1 and pointer2 are equal, we must break out of the while loop, as we have found the node where the two lists merge.

如果在任何時候，pointer1和pointer2相等，則必須打破while循環，因為我們找到了兩個列表合并的節點。

if pointer1 == pointer2:
    break

However, if it is not equal, we will move forward by utilizing .next.

但是，如果不相等，我們將利用.next向前移動。

pointer1 = pointer1.next
pointer2 = pointer2.next

As we can see from the example diagram, our first singly linked list, SLL 1, is shorter than SLL 2. So let’s suppose SLL 1 hits None before SLL 2 finds the merge node. In this case we will simply begin again, setting the same if statement for SLL 2, in case we have a test case in our program where the second SLL is the shorter one.

從示例圖中可以看到，我們的第一個單鏈列表SLL 1比SLL 2短。因此，假設SLL 1在SLL 2找到合并節點之前命中None。 在這種情況下，我們將再次開始，為SLL 2設置相同的if語句，以防程序中有一個測試用例，其中第二個SLL是較短的。

if pointer1 == None:
    pointer1 == head1
if pointer2 == None:
    pointer2 == head1

This logic of starting over will repeat in the while loop until both pointers find the merging node at the same time, or in other words, until pointer1 and pointer2 are equal. When that happens, we must remember to do what was asked of us and return the integer data value of that node.

重新開始的邏輯將在while循環中重復，直到兩個指針同時找到合并節點，或者換句話說，直到指針1和指針2相等為止。 發生這種情況時，我們必須記住執行要求我們執行的操作，并返回該節點的整數數據值。

return pointer1.data

Because this will also be pointer2’s data, we can return this in lieu of pointer1. It has the same value.

因為這也將是指針2的數據，所以我們可以代替指針1返回它。 它具有相同的值。

return pointer2.data 

執行 (Execute)

# For our reference:
#
# SinglyLinkedListNode:
#     int data
#     SinglyLinkedListNode next
#
#def findMergeNode(head1, head2):    # Set the pointers
    pointer1 = head1
    pointer2 = head2    while not None:        # if we found the merging node, then break out of the loop
        if pointer1 == pointer2:
            break        #traverse through lists
        pointer1 = pointer1.next
        pointer2= pointer2.next        # Begin again if one was shorter than the other
        if pointer1 == None:
            pointer1 = head1
        if pointer2 == None:
            pointer2 = head2    return pointer1.data

升級編碼 (Level Up Coding)

Thanks for being a part of our community! Subscribe to our YouTube channel or join the Skilled.dev coding interview course.

感謝您加入我們的社區！ 訂閱我們的YouTube頻道或參加Skilled.dev編碼面試課程 。