訪談：總結兩個鏈表中的數字

Question

在昨天的一次採訪中，我被問到如何去總結包含數字的兩個單鏈表的值。他們還表示，名單可能是不相同的長度。

我詢問列表保存倒退，因爲這就是我在大學學習了，但他們說沒有，這是存儲轉發。他們還表示，我不能簡單地顛倒名單，然後添加，然後反轉它再次前進，因爲該選項需要太多的處理。這種解決方案是我所能在網上找到的。

我無法給出一個答案，即使他們暗示我應該用遞歸函數來這樣做。

任何人都可以幫我解決這個問題。這是爲了一個C++的工作，我希望如果我得到回覆，並且能夠解釋我研究瞭解決方案，他們可能會認爲這是一個好兆頭。謝謝。

對於那些困惑的總和應該如何工作的，它以這種方式呈現。

列表1：1-> 2-> 9 列表2：1-> 3

如此以來，號碼存儲向前，我會需要通過添加兩個列表的9和3（端開始）。然後取1進，做1 + 2 + 1等等

Answer 1

你算兩個列表的長度。你在開頭填入一個數字爲0的較短列表，以便它們的長度相等。現在你用兩個數字填充一個0（它將被第一個數字的進位所使用，所以有可能9 + 1 = 10）。 您可以創建一個長度等於前兩個的第三個鏈表。

現在你做一類是這樣的：

class Digit 
{ 
    public: 
    Digit *Next; 
    int Dt; 
} 

和這樣的功能：

• 這是 「0版本」。
• 在「版本1」中，刪除最後一個進位的額外填充並僅在需要時才添加。
• 在「版本2」中，您從鏈接列表的前面刪除不必要的「0」數字。
• 在「版本3」中，您直接在Sum中創建runningTotal鏈接列表。你給第一級總和只是運行總數的「頭」。
• 在「第4版」，而不是填充所述短LL的，則傳遞（這是最困難的流路）的位數從最長LL跳過數的參數。

還有另一種可能性，更復雜，但不需要預先計算列表的長度。它使用兩個遞歸函數：

第一個遞歸函數簡單地橫貫左右，而兩者都存在。如果兩者都在同一時間完成，那麼您可以簡單地按照前面的示例進行回滾。

如果他們中的一個在另一個之前完成，那麼你用另一個這樣的遞歸功能（* extraDigits的初始值爲1）：

void SaveRemainingDigits(const Digit *remaining, int *extraDigits, int **buffer) 
{ 
    int currentDigit = *extraDigits - 1; 

    *extraDigits = *extraDigits + 1; 

    if (remaining->Next) 
    { 
     SaveRemainingDigits(remaining->Next, extraDigits, buffer);  
    } 
    else 
    { 
     *buffer = (int*)malloc(sizeof(int) * extraDigits); 
    } 

    (*buffer)[currentDigit] = remaining->Dt; 
} 

時，這個功能終於返回，我們必須從暫存器在哪裏提取數字和暫存器的長度

我們的第一個遞歸函數的最內層現在已經將最短鏈表的當前數字與暫存器的最後一個數字相加並且放置最長的當前數字在暫存器中代替剛剛使用的數字。現在，您展開遞歸函數，並使用便箋簿作爲圓形數組。展開完成後，將元素添加到RunningTotal鏈接列表中，直接從暫存器中取出它們。

正如我所說，這有點複雜，但在1-2個小時內，我可以把它寫下來作爲一個程序。

一個例子（不進位）

1 2 3 4 
6 5 

你遞歸前兩個元素。所以你有

1-6 (in the first level) 
2-5 (in the second level) 

現在你看到，第二個列表已完成，你使用第二個功能。

3 (extraDigit enters as 0, is modified to 1. currentDigit = 0) 
4 (extraDigit enters as 1, is modified to 2. currentDigit = 1. 
    malloc of 2 elements, 
    buffer[currentDigit] = 4 => buffer[1] = 4) 

unroll and we return to the previous row 

3 (currentDigit = 0 
    buffer[currentDigit] = 3 => buffer[0] = 3) 

現在我們返回到前一個功能

2-5 (in the second level, 
    with a lengthBuffer == 2, 
    we set index = length(buffer) - 1 
    currentDigitTotal = 5 + buffer[index] => currentDigitTotal = 5 + 4 
    buffer[index] = 2 => buffer[1] = 2; 
    index = (index - 1 + lengthBuffer) % lengthBuffer => index = 0 

1-6 (in the first level, 
    with a lengthBuffer == 2, 
    index = 0, 
    currentDigitTotal = 6 + buffer[index] => currentDigitTotal = 6 + 3 
    buffer[index] = 1 => buffer[0] = 1; 
    index = (index - 1 + lengthBuffer) % lengthBuffer => index = 1 

now we exited the recursive function. 
In an external function we see that we have a buffer. 
We add its elements to the head of the total. 

Our Linked list now is 9-9 and our buffer is 1,2 with index 1 

for (int i = 0; i < lengthBuffer; i++) 
{ 
    runningTotal.AddHead(buffer(index)); 
    index = (index - 1 + lengthBuffer) % lengthBuffer 
} 

Answer 2

我會創造像*頭或*尾巴來存儲我從開始的節點的地址的節點，然後遍歷列表確保我不會回到我的起點。這並不要求必須計算每個的長度，這聽起來效率低下。至於遞歸性，只要在函數頂部檢查並返回（node-> value + myfunct（node-> prev））;考慮到你一次做數學會更有效率。

Answer 3

我將在像這樣

解決這個問題讓我們假設2名列表是：
1-> 2-> 7-> 6-> 4-> 3和
5-> 7- > 2

總和爲1->2->7 + Sum(6->4->3, 5->7->2)

現在我們作出這樣的取同樣大小的2所列出並返回它們的和函數

這會像

list1->val + list2->val + Sum(list1->next, list2->next) 

與基本情況if(list1->next == NULL) return list1->val+list2->val;

注::我們可以輕鬆地處理在明年通進，也可以處理，在我們的求和函數本身畢竟這

所以我們的ans將1->2->7->11->11->5 然後遞歸地執行％10並帶進並將其添加到先前的值。

所以最終ANS將1->2->8->2->1->5

Answer 4

名單「1，2,9」和「1,3」各自表示數字「129」和「13」，在這種情況下的總和爲「142」 。

使用遞歸

• 計算每個列表的長度。
• 如果長度不同，請在開始時填充最短的零。
• 以遞歸方式迭代列表，返回：a）進位號（如果有的話），否則返回零，以及b）列表的尾部。

在僞代碼：

def sum_lists_rec(a, b, start_a, start_b, length_a, length_b): 
    """Returns a pair of two elements: carry and the tail of the list.""" 

    if the end of the lists: 
     return (0, empty_list) 

    result = sum_lists_rec(a+1, b+1, start_a+1, start_b+1, length_a, length_b) 

    carry = (a[0] + b[0] + result[0])/10 
    digit = (a[0] + b[0] + result[0]) % 10 

    return (carry, [digit] ++ result[1]) 

def sum_lists1(a, b): 
    length_a = length(a) 
    length_b = length(b) 

    if length_a < length_b: 
     a = [0, 0, ..., (length_b - length_a)] ++ a 
    else if length_b < length_a: 
     b = [0, 0, ..., (length_a - length_b)] ++ b 

    result = sum_lists_rec(a, b, length_a, length_b, 0, 0) 

    if result[0] != 0: 
     return [result[0]] ++ result[1] 
    else: 
     return result[1] 

作爲替代方案，可以使用一個堆棧：

• 計算每個列表的長度。
• 如果長度不同，請在開始時填充最短的零。
• 推送堆棧上兩個列表的每個數字。
• 彈出堆棧直到空，創建新列表。