1. 교차 연결 리스트

문제 링크: 교차 연결 리스트

먼저 코드를 살펴보겠습니다.

/**
 * 단일 연결 리스트에 대한 정의입니다.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* findIntersectionNode(struct ListNode* listA,
                                     struct ListNode* listB) {
    if (listA == NULL || listB == NULL)
        return NULL;
    ListNode *ptrA, *ptrB;
    ptrA = listA, ptrB = listB;
    while (ptrA != ptrB) {
        ptrA = (ptrA!=NULL) ? ptrA->next : listB;
        ptrB = (ptrB!=NULL) ? ptrB->next : listA;
    }
    return ptrA;
}

접근 방법:

이 문제를 해결하기 위해 이중 포인터 방법을 사용할 수 있습니다.

1. 먼저 두 연결 리스트의 헤드 노드가 비어있는지 확인합니다. 하나라도 비어있으면 두 연결 리스트는 교차할 수 없으므로 NULL을 반환합니다.
2. 두 포인터 ptrA와 ptrB를 각각 listA와 listB를 가리키도록 생성합니다.
3. 반복문을 시작하여 ptrA와 ptrB가 같은지를 조건으로 사용합니다. 반복문 내에서 ptrA와 ptrB가 NULL인 경우를 고려합니다. 만약 ptrA가 NULL에 도달하면 ptrA를 listB에서 시작하게 하고, ptrB도 마찬가지로 처리합니다. 이렇게 하면 교차 노드를 찾을 수 있습니다. 만약 두 연결 리스트가 교차하지 않는다면, ptrA와 ptrB는 동시에 NULL을 가리키게 됩니다. 마지막으로 두 포인터 중 어느 하나를 반환하면 됩니다.

2. 순환 연결 리스트

문제 링크: 순환 연결 리스트

먼저 코드를 살펴보겠습니다.

typedef struct ListNode ListNode;
bool hasCycle(struct ListNode* head) {
    ListNode* fastRunner = head;
    ListNode* slowRunner = head;
    while (fastRunner && fastRunner->next) {
        slowRunner = slowRunner->next;
        fastRunner = fastRunner->next->next;
        if (slowRunner == fastRunner) {
            return true;
        }
    }
    return false;
}

접근 방법:

1. 빠른 포인터와 느린 포인터 방법을 사용합니다. slowRunner와 fastRunner를 정의하고, slowRunner는 한 번에 한 걸음씩, fastRunner는 한 번에 두 걸음씩 이동합니다. 두 포인터는 반드시 순환 내에서 만납니다.
2. 추론: 순환에 진입하기 전에 N걸음이 필요하고, 순환의 길이가 M이라고 가정합시다. slowRunner가 순환에 진입할 때 두 포인터가 걸은 걸음 수는 slowRunner=N, fastRunner=2N입니다. 연결 리스트의 다음 포인터가 가리키는 방향을 양의 방향으로 본다면, slowRunner가 M-N만큼 앞서 있는 것입니다. 각 반복마다 fastRunner는 slowRunner에 비해 한 걸음 앞으로 나아가므로, M-N은 양의 정수이므로 두 포인터는 반드시 순환 내에서 만납니다.
3. 팁: 만약 fastRunner가 각 반복에서 slowRunner에 비해 한 걸음보다 많이 나아간다면 반드시 만나는 것은 아닙니다. 직접 추론해보세요!

3. 순환 연결 리스트 II

문제 링크: 순환 연결 리스트 II

먼저 코드를 살펴보겠습니다.

typedef struct ListNode ListNode;
struct ListNode* findCycleEntry(struct ListNode* head) {
    ListNode* runner1 = head;
    ListNode* runner2 = head;
    while(runner1 && runner1->next){
        runner1=runner1->next->next;
        runner2=runner2->next;
        if(runner1==runner2){
            runner1=head;
            while(runner1!=runner2){
                runner1=runner1->next;
                runner2=runner2->next;
            }
            return runner1;
        }
    }
    return NULL;
}

접근 방법:

위와 같이 빠른 포인터와 느린 포인터 방법을 계속 사용합니다.

1. 만약 순환이 존재한다면, 두 포인터는 순환 내에서 만납니다.
2. 두 포인터가 만난 후, 한 포인터를 다시 헤드 노드를 가리키도록 하고, 각 포인터가 한 걸음씩 이동하면 만나는 지점이 순환의 진입 지점입니다.
3. 추론: 만났을 때 runner1은 반드시 runner2보다 한 바퀴만큼 더 걸었다고 가정할 수 있습니다. runner2가 T걸음을 걸어 runner1과 만났다고 가정합시다. 순환에 진입하기 전의 연결 리스트 노드 수를 N, 순환의 길이를 M이라고 하면 다음과 같은 등식이 성립합니다:

(1) T=N+X；(2) 2T=N+X+M；(1)-(2)를 하면 M=N+X가 됩니다. 이때 runner2는 이미 순환 내에서 X걸음을 걸었으므로, 순환의 진입 지점까지는 N걸음만 더 걸으면 됩니다. 그리고 순환 이전의 노드 수가 바로 N이므로, 두 포인터가 마지막으로 만나는 노드가 바로 순환의 진입 지점입니다.

이 문제는 두 포인터가 만난 지점에서 순환을 잘라내어 두 개의 교차 연결 리스트를 만들고, 교차 연결 리스트 방법을 사용하여 해결할 수도 있습니다. 여기서는 자세히 설명하지 않겠습니다. 직접 실습해보세요!