두 수 더하기 (Add Two Numbers)
두 개의 비어 있지 않은 연결 리스트가 주어집니다. 각각은 음이 아닌 정수를 나타내며, 각 노드는 한 자리 숫자(0~9)를 담고 있습니다. 숫자는 역순(일의 자리부터)으로 저장되어 있습니다.
두 수를 더한 결과를 연결 리스트 형태로 반환하세요.
두 수는 0 자체를 제외하고는 앞자리에 0이 오지 않는다고 가정해도 됩니다.
예시 1:
입력: l1 = [2,4,3], l2 = [5,6,4]
출력: [7,0,8]
설명: 342 + 465 = 807.
Plain Text
복사
예시 2:
입력: l1 = [0], l2 = [0]
출력: [0]
Plain Text
복사
예시 3:
입력: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
출력: [8,9,9,9,0,0,0,1]
Plain Text
복사
제약 조건:
•
각 연결 리스트의 노드 개수는 [1, 100] 범위입니다.
•
0 <= Node.val <= 9
•
리스트는 앞자리에 0이 오지 않는 숫자를 표현합니다(단, 숫자 0 자체는 예외).
홀수-짝수 연결 리스트 (Odd Even Linked List)
단일 연결 리스트의 head가 주어질 때, 인덱스가 홀수인 노드들을 먼저 모은 뒤 그 다음에 인덱스가 짝수인 노드들을 이어 붙여서, 재배열된 리스트를 반환하세요.
여기서 첫 번째 노드가 홀수(odd), 두 번째 노드가 짝수(even) 로 간주되며 이후도 동일하게 번갈아갑니다.
주의: 홀수 그룹 내부, 짝수 그룹 내부에서의 상대적 순서는 입력과 동일하게 유지되어야 합니다.
추가 공간은 O(1), 시간 복잡도는 O(n)으로 해결해야 합니다.
예시 1:
입력: head = [1,2,3,4,5]
출력: [1,3,5,2,4]
Plain Text
복사
예시 2:
입력: head = [2,1,3,5,6,4,7]
출력: [2,3,6,7,1,5,4]
Plain Text
복사
제약 조건:
•
연결 리스트의 노드 개수는 [0, 10^4] 범위입니다.
•
-10^6 <= Node.val <= 10^6
두 연결 리스트의 교차점 (Intersection of Two Linked Lists)
두 단일 연결 리스트의 머리 노드 headA, headB가 주어집니다. 두 리스트가 교차한다면 처음으로 교차하는 노드를 반환하고, 교차하지 않는다면 null을 반환하세요.
예를 들어 아래와 같은 두 리스트는 c1에서 교차를 시작합니다:
테스트 케이스는 전체 연결 구조 어디에도 사이클(cycle) 이 없도록 생성됩니다.
또한 함수가 종료된 후에도 연결 리스트는 원래 구조를 유지해야 합니다.
커스텀 채점(Custom Judge):
입력은 다음과 같이 주어집니다(프로그램에는 이 값들이 직접 주어지지 않습니다):
•
intersectVal: 교차 노드의 값(교차가 없다면 0)
•
listA: 첫 번째 리스트
•
listB: 두 번째 리스트
•
skipA: listA의 head부터 교차 노드까지 건너뛰는 노드 수
•
skipB: listB의 head부터 교차 노드까지 건너뛰는 노드 수
채점기는 이 정보를 이용해 실제 연결 구조를 만든 뒤 headA, headB를 프로그램에 전달합니다. 올바른 교차 노드를 반환하면 정답 처리됩니다.
예시 1:
입력: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
출력: 교차 노드 값 = 8
설명:
A의 head에서 보면 [4,1,8,4,5], B의 head에서 보면 [5,6,1,8,4,5] 입니다.
A에서는 교차 노드(값 8) 이전에 2개의 노드가 있고, B에서는 3개의 노드가 있습니다.
- 주의: A와 B의 값이 1인 노드(각각 A의 2번째, B의 3번째)는 서로 다른 노드 참조입니다.
반면 값이 8인 노드(A의 3번째, B의 4번째)는 메모리에서 같은 노드를 가리킵니다.
Plain Text
복사
예시 2:
입력: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
출력: 교차 노드 값 = 2
설명:
A의 head에서 보면 [1,9,1,2,4], B의 head에서 보면 [3,2,4] 입니다.
A에서는 교차 노드 이전에 3개의 노드가 있고, B에서는 1개의 노드가 있습니다.
Plain Text
복사
예시 3:
입력: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
출력: 교차 없음
설명: 두 리스트가 교차하지 않으므로 null을 반환합니다.
Plain Text
복사
제약 조건:
•
listA의 노드 개수는 m개입니다.
•
listB의 노드 개수는 n개입니다.
•
1 <= m, n <= 3 * 10^4
•
1 <= Node.val <= 10^5
•
0 <= skipA <= m
•
0 <= skipB <= n
•
교차가 없다면 intersectVal = 0 입니다.
•
교차가 있다면 intersectVal == listA[skipA] == listB[skipB] 입니다.
추가 질문(Follow up):
시간 복잡도 O(m + n), 추가 메모리 O(1)로 해결할 수 있나요?