1721. Swapping Nodes in a Linked List [leetcode] | 값이 아닌 객체(노드)를 직접 교환 해보기

https://leetcode.com/problems/swapping-nodes-in-a-linked-list/description/

문제는 위 링크 참조

 

해당 문제를 처음 접근 했을 때 객체를 교환하는 것은 너무 복잡해 보여 값만 교환하는 방식으로 문제를 해결할 수 있었다.

이후 직접 객체를 교환하는 방식을 학습해보았다.

 

 

풀이 요약

1. 에지 케이스 처리: 리스트가 비어있거나 하나의 노드만 있는 경우 그대로 반환

2. dummy 노드를 생성하여 head 노드 교환을 처리

3. 4개의 포인터 사용 : prevFirst, first, prevSecond, second (각각 교환할 두 노드와 그 직전 노드들을 가리킨다.)

4. 앞에서 k번째 노드(first)와 직전 노드(prevFirst) 찾기

5. 뒤에서 k번째 노드(second)와 직전 노드(prevSecond) 찾기  (fast 포인터 사용)

6. 두 노드가 같은 경우(k가 리스트 길이의 절반일 때) 변경이 필요 없으므로 head 반환

 

 

 

1. 에지 케이스 처리

if (head == null || head.next == null) return head;

 

2. dummy 노드를 생성하여 head 노드 교환을 처리

3. 4개의 포인터 사용: prevFirst, first, prevSecond, second (각각 교환할 두 노드와 그 직전 노드들을 가리킨다.)

ListNode dummy = new ListNode(0);

dummy.next = head;

 

ListNode prevFirst = dummy;

ListNode first = head;

ListNode second = head;

ListNode prevSecond = dummy;

dummy 노드 생성, prevFirst, first, prevSecond, second 포인터 설정

 

4. 앞에서 k번째 노드(first)와 직전 노드(prevFirst) 찾기

for (int i = 1; i < k; i++) {

    prevFirst = prevFirst.next;

    first = first.next;

}

첫 번째 k번째 노드(first)와 직전 노드(prevFirst) 찾기

 

fast 포인터가 뒤에서 k 번째 노드를 찾는 것을 도와준다. 

fast.next와 second의 간격이 k, 그림상에서는 간격 2인 것을 알 수 있다.

 

 

 

5. 뒤에서 k번째 노드(second)와 직전 노드(prevSecond) 찾기  (fast 포인터 사용)

ListNode fast = first;

while (fast.next != null) {

    fast = fast.next;

    prevSecond = second;

    second = second.next;

}

second가 뒤에서 k번째 노드를 가리킴 (fast.next == null인 상황)

 

6. first와 second 노드가 같은 경우는 교환할 필요 없이 head 반환

if (first == second) return head;

 

1~6. 까지의 과정을 통해 앞, 뒤에서 각각 k번째인 노드를 찾을 수 있었다. 이제 first, second 노드의 swap을 처리하면 된다.

 

노드 교환

7.

prevFirst.next를 second로 설정

prevSecond.next를 first로 설정

 

 

prevFirst.next = second;

prevSecond.next = first;

8.first와 second의 next 포인터를 교환

 

 

ListNode temp = first.next;

first.next = second.next;

second.next = temp;

두 노드가 완전히 교환된 후의 모습

 

교환이 완료된 후 마지막으로 dummy.next를 반환하면 된다.

 

 

주의 : dummy.next가 아닌 head를 반환하면 일부 테스트 케이스에 실패한다.

Input

head = [1,2]  k = 1

Output (오답)

[1]

Expected 

[2,1]

 

실패 원인

head 노드 교환 문제

만약 k가 1이거나 리스트의 길이와 같을 경우, head 노드가 교환되어야 하는데 head를 직접 반환하면, head 노드가 교환된 경우에도 원래의 head를 가리키게 된다.

 

초기 상태: dummy -> 1 -> 2 head = 1

노드 교환 후: dummy -> 2 -> 1

head를 반환할 경우

head는 여전히 값이 1인 노드를 가리킨다.

결과: [1] (오답)