문제
| 주어진 연결 리스트에서 인접한 두 노드씩 교환한 후, 변경된 리스트의 헤드를 반환하라. 단, 노드의 값을 직접 바꾸면 안 되고, 노드 자체를 교환해야한다. |
https://leetcode.com/problems/swap-nodes-in-pairs/description/
public class SwapNodesInPairs {
public static class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public static void main(String[] args) {
ListNode node = new ListNode(1);
node.next = new ListNode(2);
node.next.next = new ListNode(3);
node.next.next.next = new ListNode(4);
node.next.next.next.next = new ListNode(5);
node.next.next.next.next.next = new ListNode(6);
ListNode result = swapNodesInPairs(node); // 구현
while(result != null) {
System.out.println(result.val);
result = result.next;
}
}
}
해결1) 반복문 사용
1-1) while문과 Dummy Node 사용 1
public static ListNode swapNodesInPairs(ListNode head) {
ListNode node = new ListNode(0);
node.next = head;
ListNode root = node;
while (node.next != null && node.next.next != null) {
ListNode a = node.next;
ListNode b = node.next.next;
// swap
a.next = b.next;
node.next = b;
node.next.next = a;
// move
node = node.next.next;
}
return root.next;
}
while문과 Dummy Node (= node, ListNode(0)) 을 사용하여 두 노드의 쌍을 swap 할 수 있습니다.
인자로 넘겨 받은 연결 리스트의 head 노드를 Dummy Node (node) 뒤에 연결하고
node 를 기준으로 그 다음 노드(a) 와 그 다음 다음 노드(b) 의 포인터를 swap 합니다.
swap 이 완료되면 다음 두 노드의 쌍을 swap 해야 하므로 두 노드 뒤로 이동합니다.
조금 더 구체적으로 이야기하면,
(1) a 노드의 다음을 b 노드의 다음으로 연결한다
(2) 기준 노드의 다음을 b로 연결한다
(3) 기준 노드의 다음 다음(b.next)을 a로 연결한다.
1-2) while문과 Dummy Node 사용 2
public static ListNode swapNodesInPairsAnotherAnswer(ListNode head) {
ListNode node = new ListNode(0);
node.next = head;
ListNode root = node;
while (node.next != null && node.next.next != null) {
ListNode a = node.next;
ListNode b = node.next.next;
// swap
a.next = b.next;
b.next = a;
node.next = b;
// move
node = node.next.next;
}
return root.next;
}
while 문과 Dummy Node(= node, ListNode(0)) 을 사용하여 swap 하는 또 다른 방식의 풀이입니다.
위 방식과 크게 다르지 않습니다. (순서만 다릅니다)
다만 swap 부분에서 node를 기준으로 연결 관계(=포인터)를 변경하는 것이 아니라,
a 노드와 b노드의 연결 관계를 swap 한 뒤(b -> a) 맨 앞의 기준 노드(node)의 다음을 b로 변경하는 것입니다.
구체적으로 살펴보면,
(1) a 노드의 다음을 b 노드의 다음으로 연결한다
(2) b 노드의 다음을 a 노드로 연결한다
(3) 기준 노드의 다음을 b 노드로 연결한다
그리고 동일하게 swap이 완료되면 두 노드 뒤로 이동합니다.
해결2) 재귀함수 사용
public static ListNode swapNodesInPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// swap
ListNode tmp = head.next;
head.next = swapNodesInPairs(head.next.next); // recursive call
tmp.next = head;
return tmp;
}
while 문(반복문)을 사용하지 않고 재귀 함수를 사용하여 해결할 수도 있습니다.
코드만 봐서는 직관적으로 이해하기가 다소 어렵기 때문에 풀어서 설명하겠습니다.
| LinkedList
| 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null |
| STEP1 : 시작
| head = 1, head.next = 2, swapNodesInPairs(3) |
tmp = head.next(2)
head(1).next = swapNodesInPairs(3) // ↖︎ 재귀 호출 결과 : 4 -> 3 -> 5 -> 6 -> null (* 1 -> 4 -> 3 -> 6 -> 5 -> null 완성 *)
| STEP2 : swapNodesInPairs(3) 내부 로직
| head = 3, head.next = 4, swapNodesInPairs(5) |
tmp = head.next(4)
head(3).next = swapNodesInPairs(5) // ↖︎ 재귀 호출 결과 : 6 -> 5 -> null (* 3 -> 6 -> 5 -> null 완성 *)
| STEP3 : swapNodesInPairs(5) 내부 로직
| head = 5, head.next = 6, swapNodesInPairs(null) |
tmp = head.next(6)
head(5).next = swapNodesInPairs(null) // ↖︎ 재귀호출 결과 : null (* 5 -> null 완성 *)
| STEP4 : swapNodesInPairs(null) 내부로직
| head = null |
if (head == null) -> return head // (null) 리턴 ↖︎
tmp(6).next = head(5)
return tmp // (6 -> 5 -> null) 리턴 ↖︎
tmp(4).next = head(3)
returm tmp // (4 -> 3 -> 6 -> 5 -> null) 리턴 ↖︎
tmp(2).next = head(1)
return tmp // 최종 결과로 (2 -> 1 -> 4 -> 3 -> 6 -> 5 -> null) 리턴
마무리하며
재귀 함수는 코드로 얼핏 보았을 때는 간단해보이지만, 한번에 생각해내거나 이해하기가 생각보다 까다로운 것 같습니다. 다음 함수 호출에 변수의 값은 어떻게 할당되고, 최종 리턴 값은 어떻게 만들어지는지 그리고 리턴 결과를 호출부에서 어떻게 활용하는지 그림으로 그려보는 것이 이해하는데 큰 도움이 되는 것 같습니다.
그리고 swap을 할 때에는 꼭 이전 변수의 값을 미리 담아둘 임시 변수가 필요하다는 것을 기억해두면 좋을 것 같습니다.
'PS > Leetcode' 카테고리의 다른 글
| 15. 세 수의 합(3 Sum) (0) | 2025.03.13 |
|---|
