[algorithm] 두 개의 연결 목록이 병합되는지 확인하십시오. 그렇다면 어디?

만약

• “수정이 허용되지 않음”은 “변경할 수 있지만 결국 복원되어야 함”을 의미하며
• 목록을 정확히 두 번 반복 할 수 있습니다.

다음 알고리즘이 해결책이 될 것입니다.

첫째, 숫자. 제리스트의 길이라고 가정 a+c하고, 두 번째의 길이이며 b+c, c(mergepoint 후) 공통의 “꼬리”의 길이이다. 다음과 같이 표시하겠습니다.

x = a+c
y = b+c

우리가 길이를 알 수 없기 때문에, 우리는 계산합니다 x및 y추가 반복없이; 당신은 방법을 볼 수 있습니다.

그런 다음 각 목록을 반복하고 반복하는 동안 되돌립니다! 두 반복자가 동시에 병합 지점에 도달하면 단순히 비교를 통해 알아냅니다. 그렇지 않으면 한 포인터가 다른 포인터보다 먼저 병합 지점에 도달합니다.

그 후 다른 반복기가 병합 지점에 도달하면 공통 꼬리로 진행되지 않습니다. 대신 이전에 병합 지점에 도달했던 목록의 이전 시작으로 돌아갑니다! 따라서 변경된 목록의 끝에 도달하기 전에 (즉, 다른 목록의 이전 시작 부분) a+b+1반복을 합산합니다. 그것을라고 부르 자 z+1.

병합 지점에 먼저 도달 한 포인터는 목록 끝에 도달 할 때까지 계속 반복됩니다. 반복 횟수를 계산해야하며과 같습니다 x.

그런 다음이 포인터는 역순으로 목록을 다시 반전합니다. 그러나 이제는 원래 시작된 목록의 처음으로 돌아 가지 않습니다! 대신 다른 목록의 처음으로 이동합니다! 반복 횟수를 계산하고 y.

따라서 우리는 다음 숫자를 알고 있습니다.

x = a+c
y = b+c
z = a+b

우리가 결정하는 것으로부터

a = (+x-y+z)/2
b = (-x+y+z)/2
c = (+x+y-z)/2

문제가 해결됩니다.

답변

lenA = count(listA) //iterates list A
lenB = count(listB) //iterates list B

ptrA = listA
ptrB = listB

//now we adjust either ptrA or ptrB so that they are equally far from the end
while(lenA > lenB):
    ptrA = ptrA->next
    lenA--
while(lenB > lenA):
    prtB = ptrB->next
    lenB--

while(ptrA != NULL):
    if (ptrA == ptrB):
        return ptrA //found merge point
    ptrA = ptrA->next
    ptrB = ptrB->next

A-->B-->C
        |
        V
1-->2-->3-->4-->5

A   B   C

1-->2-->3   4   5

for each item in list a
  push pointer to item onto stack_a

for each item in list b
  push pointer to item onto stack_b

while (stack_a top == stack_b top) // where top is the item to be popped next
  pop stack_a
  pop stack_b

// values at the top of each stack are the items prior to the merged item