通過顛倒列表查找兩個列表的合併點

Question

問題描述： 給出指向兩個鏈接列表的頭節點的指針，這兩個鏈接列表在某個節點上合併在一起。找到發生此合併的節點。兩個頭節點將會不同，都不會爲NULL。

輸入格式 您必須完成int FindMergeNode（Node * headA，Node * headB）方法，該方法接受兩個參數 - 鏈接列表的頭部。你不應該讀取標準輸入/控制檯的任何輸入。

輸出格式 查找兩個列表合併並返回該節點的數據的節點。不要將任何東西打印到標準輸出/控制檯。

我想扭轉這兩個列表，然後分別走過他們每個人，直到我到達最後一個公共節點。但是在測試時，它沒有給出正確的輸出。 我的想法是錯的還是我的代碼錯了？這是一個好方法還是壞方法？

我的代碼：

int FindMergeNode(Node headA, Node headB) { 

//Reverse listA 
Node currentA = headA; 
Node prevA = null; 
Node NextA; 
while(currentA!=null){ 
    NextA = currentA.next; 
    currentA.next = prevA; 
    prevA = currentA; 
    currentA = NextA; 
} 
headA = prevA; 

//Reverse listB 
Node currentB = headB; 
Node prevB = null; 
Node NextB; 
while(currentB!=null){ 
    NextB = currentB.next; 
    currentB.next = prevB; 
    prevB = currentB; 
    currentB = NextB; 
} 
headB = prevB; 

//Iterate throught the reversed list and find the last common node. 
Node n = headA; 
Node m = headB; 
while(n.next!=m.next){ 
    n = n.next; 
    m = m.next; 
} 

return n.data; 
} 

鏈接問題：https://www.hackerrank.com/challenges/find-the-merge-point-of-two-joined-linked-lists

編輯：從KARTHIK的回答，我修改了第三while循環，但它畢竟是給了錯誤的輸出。

//Iterate throught the reversed list and find the last common node. 
Node n = headA; 
Node m = headB; 
while(n.next == m.next){ 
    n = n.next; 
    m = m.next; 
} 

return n.data; 

Answer 1

編輯：你應該已經更加明確你的解釋。因爲通過merge，如果你的意思是合併價值，倒車方法的作品。但是如果你的意思是合併實際節點，顯然反轉方法不起作用，因爲當你反轉列表時，merging point只能有下一個指針。

A->B->C 
      \ 
      I->J->K 
     /
    X->Y 

如果這是你的列表中，當你扭轉你可不能兼得C和Y當你扭轉你的下一個pointer.Because你的樹將成爲

   A<-B<-C 
         I<-J<- K 
       X <-Y 

但是你I將指向取決於哪一個在後面被逆轉，可以是Y或C。

另一種更簡單的方法（實施方式）將其推入節點兩個stack S和一旦你完成所有的節點開始pop荷蘭國際集團的元素，並返回這是相同的最後一個節點。

Stack<Node> stackA - push all elements of listA into stackA; 
Stack<Node> stackB - push all elements of listB into stackA; 

Node result=null; 
while(stackA.peek() == stackB.peek()){ 
    result = stackA.pop(); 
    stackB.pop(); 
} 
return result; 

下面的解釋回答你原來的問題

我沒有檢查你的reversing the list邏輯，但（3 while環）後while循環肯定是錯誤的：

while(n.next!=m.next){ 
    n = n.next; 
    m = m.next; 
} 

的要點 - 它應該是n.next == m.next

// ideally you should also check (n!=null && m!=null) 
    // it handles the case where there is no common point 
    while(n!=null && m!=null && n.next == m.next){ 
    n = n.next; 
    m = m.next; 
} 
return (n == null || m == null)? null : n; 

，因爲你想找到不同的第一個節點並返回前一個節點。

Answer 2

我也有從here這個問題，我最快的解決方案：

int FindMergeNode(Node headA, Node headB) { 
    int s1 = getSize(headA), s2 = getSize(headB); 
    for(int i = 0; i<Math.abs(s1-s2); i++){ 
     if(s1>s2) headA = headA.next; 
     else headB = headB.next; 
    } 
    while(headA!=null){ 
     if(headA==headB) return headA.data; 
     headA = headA.next; 
     headB = headB.next; 
    } 
    return 0; 

} 
int getSize(Node head){ 
    int i = 0; 
    while(head!=null){ 
     head = head.next; 
     i++; 
    } 
    return i; 
}