合併兩個已排序的鏈接列表

假設列表'A'是1-> 3-> 5並且列表'B'是4-> 6-> 7 如何處理將它們合併爲需要在排序後需要排序的條件合併我想和大家分享我對這個觀點，請讓我知道，如果它需要改進，合併兩個已排序的鏈接列表

i) Compare first node of 'B' with each node of 'A' 
while A.val<B.val 
A=A.next 
We get 'A' pointing to node whose value is lesser than node of 'B' 
ii) As per the example, intent is to store '4' in '3' 's reference and prior to that store '3' 's reference in a temp 

iii) The same will have to be done for nodes in 'A', as in '5' will have to be stored between 4 and 6

請仔細閱讀這一點，並幫助我在即興

來源

2017-05-05 Ashwin V

這是相當不完整的。 –

「比較'B'的第一個節點和'A'的每個節點。」 - 你只需要比較頭部。刪除A和B的最小頭並將其附加到結果列表中。重複，直到A或B中的一個爲空。追加另一個列表到你的結果。 –

@YvesDaoust這就是爲什麼我發佈這個問題，以幫助我完成這一點，並即興創作 –

Node MergeLists(Node list1, Node list2) { 
    if (list1 == null) return list2; 
    if (list2 == null) return list1; 

    if (list1.data < list2.data) { 
    list1.next = MergeLists(list1.next, list2); 
    return list1; 
    } else { 
    list2.next = MergeLists(list2.next, list1); 
    return list2; 
    } 
}

從Interview: Merging two Sorted Singly Linked List

你不會找到比我想的遞歸更清晰的算法。

如果你想去迭代的方式，你也有我鏈接到你的帖子中的另一個答案。

來源

2017-05-05 09:01:48 rilent

合併兩個已排序的鏈接列表

回答

相關問題