연결 리스트에서 노드 삭제
문제 설명
단일 연결 리스트 head가 주어지고, 그 안에서 특정 노드 node를 삭제하려고 합니다.
•
*삭제할 노드 node*만 주어지며, 리스트의 첫 번째 노드(head)에는 접근할 수 없습니다.
•
연결 리스트의 값들은 모두 서로 다르며, 주어진 노드 node는 마지막 노드가 아님이 보장됩니다.
node를 “삭제”한다는 것은 메모리에서 완전히 없애는 것이 아니라, 리스트 상에서 다음 조건을 만족하도록 만드는 것을 의미합니다.
1.
삭제한 노드의 값이 더 이상 리스트에 존재하지 않아야 합니다.
2.
리스트의 노드 수가 1개 감소해야 합니다.
3.
node 이전의 값들은 순서를 유지해야 합니다.
4.
node 이후의 값들도 순서를 유지해야 합니다.
커스텀 테스트 규칙
•
입력으로 **전체 연결 리스트 head*와 **삭제할 노드 node*를 제공합니다.
•
node는 리스트에 실제로 존재하며 꼬리 노드가 아닙니다.
•
채점 시스템이 연결 리스트를 만든 뒤, 삭제 함수에 node를 전달합니다.
•
반환값은 삭제 함수 호출 후의 전체 리스트입니다.
예시 1
입력: head = [4,5,1,9], node = 5
출력: [4,1,9]
설명: 값이 5인 두 번째 노드를 삭제해야 하므로,
호출 후 리스트는 4 -> 1 -> 9 가 됩니다.
Plain Text
복사
예시 2
입력: head = [4,5,1,9], node = 1
출력: [4,5,9]
설명: 값이 1인 세 번째 노드를 삭제해야 하므로,
호출 후 리스트는 4 -> 5 -> 9 가 됩니다.
Plain Text
복사
제약 사항
•
연결 리스트의 노드 수: 2 ≤ n ≤ 1000
•
노드 값 범위: 1000 ≤ Node.val ≤ 1000
•
각 노드의 값은 유일합니다.
•
삭제할 노드는 리스트에 존재하며, 꼬리 노드가 아닙니다.
Remove Nth Node From End of List
연결 리스트의 head가 주어졌을 때, 뒤에서 n번째 노드를 삭제하고 새로운 head를 반환하세요.
예시
예시 1
입력: head = [1,2,3,4,5], n = 2
출력: [1,2,3,5]
설명: 뒤에서 두 번째 노드인 4를 삭제합니다.
Plain Text
복사
예시 2
입력: head = [1], n = 1
출력: []
설명: 유일한 노드인 1을 삭제하면 리스트가 비어집니다.
Plain Text
복사
예시 3
입력: head = [1,2], n = 1
출력: [1]
설명: 뒤에서 첫 번째 노드인 2를 삭제합니다.
Plain Text
복사
제약 조건
•
리스트 노드 수 sz: 1 ≤ sz ≤ 30
•
노드 값: 0 ≤ Node.val ≤ 100
•
삭제할 위치 n: 1 ≤ n ≤ sz
추가 질문 (Follow-up)
이 문제를 한 번의 리스트 순회(one pass) 로 해결할 수 있나요?
해설 요약
•
일반적으로는 리스트 전체 길이를 먼저 구한 다음 (length - n)번째 노드를 삭제하는 방식으로 해결합니다. (두 번 순회)
•
하지만 투 포인터(two pointers) 를 이용하면 한 번의 순회로도 가능합니다.
투 포인터를 이용한 한 번의 순회 (아이디어)
1.
fast 포인터를 먼저 n칸 이동시킵니다.
2.
그 뒤 fast와 slow를 함께 이동시킵니다.
3.
fast가 끝에 도달하면, slow는 삭제할 노드의 이전 노드에 도달합니다.
4.
그 다음 slow.next = slow.next.next로 노드를 삭제합니다.
Reverse Linked List
단일 연결 리스트의 head가 주어졌을 때,
해당 리스트를 뒤집은(reverse) 후, 새로운 head 노드를 반환하는 문제입니다.
예시
예시 1
•
입력: head = [1,2,3,4,5]
•
출력: [5,4,3,2,1]
→ 리스트가 완전히 반대 순서로 뒤집힙니다.
예시 2
•
입력: head = [1,2]
•
출력: [2,1]
예시 3
•
입력: head = []
•
출력: []
→ 리스트가 비어 있으면 결과도 비어 있음.
제약 조건
•
연결 리스트의 노드 수는 0개 이상 5000개 이하
•
각 노드의 값은 5000 이상 5000 이하
추가 질문 (Follow-up)
이 문제는 반복문 방식 또는 재귀 방식 중 어떤 방식으로도 풀 수 있습니다.
→ 둘 다 구현할 수 있나요? 라는 질문이 뒤따릅니다.
필요하시면 원문 그대로도 정리해드릴게요.
Merge Two Sorted Lists
설명
정렬된 두 개의 연결 리스트 list1과 list2의 head 노드가 주어집니다.
이 두 리스트를 하나의 정렬된 연결 리스트로 병합하세요.
병합된 리스트는 기존 노드들을 연결(splice) 하여 만들어야 하며,
새로운 리스트의 head 노드를 반환해야 합니다.
예시
예시 1
•
입력: list1 = [1,2,4], list2 = [1,3,4]
•
출력: [1,1,2,3,4,4]
→ 두 리스트를 정렬을 유지하면서 병합한 결과입니다.
예시 2
•
입력: list1 = [], list2 = []
•
출력: []
→ 둘 다 비어 있으면 결과도 비어 있음.
예시 3
•
입력: list1 = [], list2 = [0]
•
출력: [0]
→ 한 리스트가 비어 있으면 나머지 리스트가 결과가 됩니다.
제약 조건
•
두 리스트의 노드 수는 각각 0 이상 50 이하
•
각 노드의 값은 100 이상 100 이하
•
list1과 list2는 각각 오름차순(비내림차순) 으로 정렬되어 있음
원하시면 이 문제도 코드 없이 시각적으로 구조를 설명드릴 수 있습니다.
Palindrome Linked List
설명
단일 연결 리스트의 head가 주어졌을 때,
해당 리스트가 앞에서 읽으나 뒤에서 읽으나 같은지 — 즉, 회문(palindrome) 인지 판단하여
true 또는 false를 반환하세요.
예시
예시 1
•
입력: head = [1,2,2,1]
•
출력: true
→ 앞에서 읽든 뒤에서 읽든 [1,2,2,1]로 동일하므로 회문입니다.
예시 2
•
입력: head = [1,2]
•
출력: false
→ 앞에서 읽으면 [1,2], 뒤에서 읽으면 [2,1]로 다르기 때문에 회문이 아닙니다.
제약 조건
•
리스트의 노드 수: 1 이상 10⁵ 이하
•
각 노드의 값: 0 이상 9 이하
추가 질문 (Follow-up)
이 문제를
•
시간 복잡도 O(n)
•
공간 복잡도 O(1)
로 해결할 수 있을까요?
(즉, 리스트를 추가 저장하지 않고 회문인지 판별할 수 있는지에 대한 도전 과제가 주어집니다.)
필요하시면 회문 판단의 직관적인 방식이나 그림 설명도 제공해드릴 수 있어요.
Linked List Cycle
설명
연결 리스트의 head가 주어질 때,
해당 리스트 안에 사이클(cycle) 이 존재하는지 판단하여
true 또는 false를 반환하세요.
사이클이란?
•
연결 리스트의 어떤 노드의 next 포인터가 이전에 나왔던 노드를 가리키게 되는 경우를 사이클이라고 합니다.
•
즉, next를 계속 따라가면 끝이 아니라 계속 반복해서 순환하게 되는 구조입니다.
•
내부적으로 pos라는 값은 테스트용으로, 리스트의 끝 노드(tail)가 연결된 인덱스를 나타냅니다.
(단, pos는 함수 매개변수로 주어지지는 않습니다.)
예시
예시 1
•
입력: head = [3,2,0,-4], pos = 1
•
출력: true
→ 마지막 노드(-4)가 두 번째 노드(인덱스 1, 값 2)를 가리켜 사이클 존재
예시 2
•
입력: head = [1,2], pos = 0
•
출력: true
→ 마지막 노드(2)가 첫 번째 노드(1)를 가리켜 사이클 존재
예시 3
•
입력: head = [1], pos = -1
•
출력: false
→ 다음 노드가 없고, 사이클 없음
제약 조건
•
리스트의 노드 수는 0 이상 10⁴ 이하
•
각 노드의 값은 10⁵ 이상 10⁵ 이하
•
pos는 -1 (사이클 없음) 또는 유효한 인덱스입니다
추가 질문 (Follow-up)
이 문제를 O(1)의 메모리 사용량, 즉 상수 공간으로 해결할 수 있나요?
(별도의 해시셋 없이, 포인터만으로 사이클을 감지할 수 있는지 묻는 질문입니다.)
