查找两个链表合并点的代码

Question

FindMergePoint() 的前向声明

int FindMergePoint(Node *Larger,int largeCount,Node *Smaller,int SmallCount);

计算两个列表长度的函数，根据大小将列表传递给 FindMergePoint()，这将 return 交集节点。

    int FindMergeNode(Node *headA, Node *headB)
    {
        Node *PTRA = headA;
    Node *PTRB = headB;
    int count1 = 0,count2 = 0;
    //Count List One
    while(PTRA != NULL){
        count1++;
        PTRA = PTRA->next;
    }
    //Count List Two
    while(PTRB != NULL){
        count2++;
        PTRB = PTRB->next;
    }
    //If First list is greater
    if(count1 >= count2){
        return FindMergePoint(headA,count1,headB,count2);
    }
    else{//Second is greater
        return FindMergePoint(headB,count2,headA,count1);
    }
}

获取更大和更小列表并找到合并点的函数

 int FindMergePoint(Node *Larger,int largeCount,Node *Smaller,int SmallCount){
    Node *PTRL = Larger;
    //Now traversing till both lists have same length so then we can move 
parallely in both lists
    while(largeCount != SmallCount){
        PTRL = PTRL->next;
        largeCount--; 
    }
    Node *PTRS = Smaller;
    //Now PTRL AND PTRS WERE SYNCHRONIZED
    //Now,Find the merge point     
    while(PTRL->next != PTRS->next){
        PTRL = PTRL->next;
        PTRS = PTRS->next;
    }
    return PTRL->data;
}

Answer 1

FindMergeNode 处的代码块导致了问题

while(PTRL->next != PTRS->next) {
    PTRL = PTRL->next;
    PTRS = PTRS->next;
}

比方说，PTRL 和 PTRS

有以下条目

PTRL -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
PTRS -> 17 -> 6 -> 7 -> 8

现在，根据您的实施，PTRL 将前进 4 次 （较小链表的长度）并将指向 5。然后，您的逻辑检查 next of PTRL（指向 6）是否等于 next of PTRS（指向 6）。如果它们相等（它们是相等的，因为它们都指向 6），则 PTRL 的方法 returns data 在该点为 5。

将 while 循环中的条件更改为 PTRL != PTRS，我认为这应该可以解决您的问题。

查找两个链表合并点的代码

Code to Find the Merge Point of Two linked Lists

c++

merge

linked-list

data-structures

singly-linked-list