연결 리스트 코딩테스트: 포인터를 바꾸기 전에 다음 노드를 보존하기

연결 리스트 문제에서 포인터를 먼저 바꾸면 아직 방문하지 않은 나머지 노드로 가는 유일한 경로를 잃을 수 있습니다. 역순, 병합, 삭제 문제는 모두 “현재 노드를 어느 곳에 연결할까”보다 먼저 “다음에 읽을 노드를 어떻게 보존할까”를 결정해야 합니다. 이 글은 한 노드씩 포인터를 갱신하는 규칙과 더미 노드의 역할, 경계 테스트를 함께 추적합니다. 먼저 단일 연결 리스트 역순 질문을 코드로 풀어 보세요.

먼저 리스트의 계약과 참조를 적는다 (Node contract)

연결 리스트는 각 노드가 값과 다음 노드 참조를 갖고, head가 첫 노드를 가리키는 구조입니다. 포인터 갱신은 단순 대입처럼 보여도 이전 간선의 도달 가능성을 없앨 수 있습니다. 문제를 읽을 때 노드 수, 빈 리스트·단일 노드, 중복 값 허용, 원본 변경 가능 여부, 노드 복사 여부를 먼저 표시하세요.

기술 사실: 단일 연결 리스트는 다음 방향으로만 이동할 수 있습니다. 한 노드의 next를 덮어쓰면 이전에 저장해 두지 않은 successor로는 더 이상 그 참조에서 도달하지 못할 수 있습니다. 후보자 보고: 이번 글은 특정 채용 전형이나 실제 질문을 주장하기 위한 후보자 보고를 사용하지 않습니다. 추론: 인터뷰에서는 “다음 노드를 먼저 저장하는 이유”를 도달 가능성이라는 불변식으로 설명하면 코드 순서가 근거를 갖습니다.

순회 불변식: 처리한 부분과 남은 부분 (Reversal invariant)

역순 알고리즘에서는 매 단계 직전에 prev가 이미 뒤집힌 prefix의 새 head이고, cur가 아직 처리하지 않은 suffix의 첫 노드입니다. nxt = cur.next를 먼저 저장한 뒤 cur.next = prev로 간선을 뒤집고, 마지막에 prev, cur = cur, nxt로 진행합니다. 갱신 순서를 바꾸면 cur.next에 있던 suffix의 시작점을 잃을 수 있습니다.

포인터를 안전하게 뒤집는 구현 (Iterative reversal)

class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node

def reverse(head):
    prev = None
    cur = head
    while cur is not None:
        nxt = cur.next       # 남은 suffix의 시작점을 먼저 보존
        cur.next = prev      # 현재 간선만 역방향으로 바꿈
        prev = cur
        cur = nxt
    return prev

입력 A → B → C → null에서 첫 반복 전에는 prev=null, cur=A, nxt=B입니다. A.next를 null로 바꿔도 nxt가 B를 붙잡고 있으므로 다음 반복이 가능합니다. 다음에는 B.next=A, 마지막에는 C.next=B가 되어 C → B → A → null이 됩니다. 반복 후의 불변식은 처리한 prefix가 올바르게 뒤집혔고, 미처리 suffix의 모든 노드가 cur에서 계속 도달 가능하다는 것입니다.

경계를 먼저 잡는 더미 노드 (Dummy node)

리스트의 첫 노드를 삭제하거나 결과 head가 바뀌는 문제는 별도 분기를 늘리는 대신 더미 노드가 도움이 됩니다. dummy.next = head로 시작하면 첫 노드 앞에도 “이전 노드”가 생깁니다. 삭제할 때 prev.next = prev.next.next로 연결을 건너뛰고, 반환은 언제나 dummy.next로 통일합니다. 삭제할 대상이 없거나 첫 노드인 경우에도 경계가 단순해집니다.

다만 더미 노드는 임의의 인덱스나 successor를 자동으로 보장하지 않습니다. prev.next가 존재하는지 검사하고, 삭제 전 다음 링크를 읽을 수 있는 상태인지 확인해야 합니다. C++에서는 해제된 노드의 iterator/reference를 다시 역참조하면 안 됩니다. Java의 가비지 컬렉션은 수동 해제와 다르지만, 제거한 노드의 참조가 남아 있거나 컬렉션 변경 뒤 iterator 계약이 깨지는 문제까지 해결하지는 않습니다. C에서는 해제 전에 successor를 보존하고 그 뒤 링크를 갱신해야 합니다.

병합에서는 입력 두 개를 모두 보존한다 (Stable merge)

정렬 리스트 병합은 두 현재 노드 중 작은 값을 결과 뒤에 붙입니다. 노드 재사용 방식을 택했다면 선택한 노드를 결과에 연결하기 전에 그 노드의 기존 next를 보존합니다. 그 뒤 해당 입력 포인터만 다음 노드로 옮깁니다. 남은 한 입력은 뒤에 그대로 연결할 수 있지만, 이 판단은 입력이 각각 오름차순이고 노드 소유권을 이전해도 된다는 계약이 있을 때만 맞습니다.

중복 값의 순서를 보존해야 한다면 동률일 때 어느 리스트를 우선하는지도 명시합니다. 새 노드를 만들면 원본은 유지되지만 추가 공간이 들고, 기존 노드를 이어 붙이면 공간을 절약할 수 있지만 입력을 파괴적으로 변경합니다. 단순히 “merge는 O(n+m)”이라고 끝내지 말고 반환 객체와 입력 변경 정책까지 설명하세요.

삭제와 그룹 역순에서 next를 잃지 않는 법 (Deletion and groups)

노드 삭제는 삭제 대상 자체보다 그 직전 노드가 핵심입니다. prev.next가 삭제할 target을 가리킨다면 after = target.next를 먼저 읽고 prev.next = after로 우회합니다. 메모리를 수동 관리하는 언어에서는 그 뒤에 target을 해제해야 하며, 해제한 뒤 target.next를 읽으면 안 됩니다.

k개 그룹 역순은 먼저 현재 그룹이 실제로 k개인지 확인합니다. 마지막 그룹이 짧고 유지 대상이라면 역순 함수에 넘기기 전 부족한 길이를 판정해야 합니다. 그룹 앞의 이전 tail, 그룹의 시작, 그룹 끝의 다음 노드, 역순 후 새 tail을 각각 이름 붙이면 마지막 불완전 그룹과 리스트 head 변경을 독립적으로 처리할 수 있습니다.

복잡도는 포인터 수와 공간 정책으로 설명 (Complexity)

반복 역순은 각 노드를 한 번 읽고 일정한 참조 대입을 하므로 O(n) 시간, O(1) 보조 공간입니다. 재귀 방식도 노드를 한 번 처리하지만 호출 스택이 O(n)까지 쌓입니다. 새 리스트로 병합하거나 복사하면 결과 노드 수에 비례하는 추가 공간이 들고, 노드 재사용 병합은 입력의 노드를 결과로 이전하는 방식입니다.

이 경계는 구현에 종속됩니다. 자동 메모리 관리 언어라고 해서 논리적 참조 손실이 없어지는 것은 아니며, 수동 메모리 관리에서는 노드 해제 순서가 안전성 조건을 더합니다. std::forward_list처럼 선행 노드 기준으로 삭제하는 API도 있으므로, 특정 표준 라이브러리의 계약을 연결 리스트 일반 규칙으로 확대하지 마세요.

흔한 오답을 상태 추적으로 고친다 (Failure traces)

• cur.next = prev부터 실행해 놓고 successor를 읽으려 한다: 나머지 suffix로 가는 참조를 잃습니다.
• 루프에서 cur = cur.next로 진행한다: 간선이 이미 이전 노드를 향하므로 역방향으로 되돌아가거나 종료하지 못할 수 있습니다. nxt로 이동하세요.
• head를 고정해 반환한다: 역순 후에는 원래 head가 tail입니다. 새 head는 prev입니다.
• 삭제 후 target.next를 다시 읽는다: 수동 해제 언어에서 이미 해제된 메모리일 수 있습니다. 먼저 after를 저장합니다.
• 값만 비교하고 노드 identity를 무시한다: 값이 중복이면 잘못된 노드를 연결해도 샘플 출력은 우연히 같을 수 있습니다.

제출 전 테스트: 값뿐 아니라 간선 확인 (Identity tests)

테스트는 빈 리스트, 한 노드, 두 노드, 홀수·짝수 길이, 중복 값, tail에서 끝나는 입력을 포함하세요. 역순 뒤에는 결과 노드 수가 입력과 같고, 모든 입력 노드가 정확히 한 번 나타나며, 새 tail의 next가 null인지 확인합니다. 단순히 값 배열만 비교하면 노드 누락·중복 연결·사이클을 놓칠 수 있으므로 최대 n+1번만 따라가며 사이클 여부도 검사하세요.

병합은 한쪽이 비었을 때, 두 값이 같은 때, 한 리스트가 완전히 먼저 끝날 때를 시험합니다. 노드 재사용이면 원본 head와 결과가 alias 되는지 기대값을 적고, 원본 보존 방식이면 결과 노드 객체가 원본과 분리됐는지도 확인합니다. 삭제는 head·tail·유일 노드 제거와 대상 없음, 그룹 역순은 길이가 k보다 짧은 마지막 구간이 핵심 반례입니다.

답변 순서: 상태·갱신·검증 (Answer structure)

면접에서는 (1) 노드 소유권과 입력 변경 조건, (2) 처리 prefix와 남은 suffix 불변식, (3) nxt를 먼저 저장하는 이유, (4) head/tail 및 빈 입력 처리, (5) 시간·공간 복잡도, (6) 간선 또는 identity까지 확인하는 테스트 순으로 설명하세요. “포인터를 조심한다”가 아니라 어떤 참조를 언제 잃을 수 있는지 말하는 답이 더 검증 가능합니다.

아래 연습 문제는 리스트의 역순, 병합, 제거, 깊은 복사, 원본 보존을 다룹니다. 공개 PracHub 질문은 학습 소재이며 특정 회사의 실제 면접 출제 기록으로 취급하지 마세요.

다음 연습 (Next exercise)

작은 리스트 1 → 2 → 3을 종이에 그리고, 각 반복 전후의 prev, cur, nxt를 표로 채우세요. 이어서 삭제 대상이 head인 경우와 그룹 끝이 부족한 경우를 같은 표기법으로 추적합니다. 이 연습은 포인터 대입의 순서를 암기하는 대신, 어떤 노드에 도달할 수 있어야 하는지 불변식으로 설명하게 해 줍니다.

Sources and Further Reading

• MIT 6.006, Data Structures and Dynamic Arrays lecture notes — 연결 리스트 노드와 포인터 기반 구조의 기초.
• Princeton Algorithms: Bags, Queues, and Stacks — 단일 연결 리스트로 큐·스택을 구현하는 예.
• C++ draft N4860, forward_list — erase_after와 iterator 유효성의 표준 문맥.
• C++ working draft: forward_list modifiers — 제거된 원소의 iterator/reference 무효화와 erase_after의 선행 조건·반환값.

근거 범위: 출처는 일반 자료구조와 C++ API 규칙을 뒷받침합니다. 후보자 보고는 수집하지 않았고 모든 포인터 추적은 교육용 합성 예제입니다. 실제 테스트 플랫폼의 입력·노드 표현은 문제별 계약을 확인하세요.