LeetCode: 24번 (Swap Nodes in Pairs) [JAVA]

문제 링크

https://leetcode.com/problems/swap-nodes-in-pairs/

Swap Nodes in Pairs - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 연결리스트의 노드를 뒤집는 swap 함수 생성 (인자는 ListNode)
2. 해당 들어온 노드가 null인 경우 그대로 null 반환, 들어온 노드의 다음이 없는 경우 뒤집을 수가 없기 때문에 해당 노드 반환
3. 그 외의 경우 현재 들어온 노드와 그 다음 노드의 순서를 바꾸는 과정을 진행, 다만 이 때 두 노드를 제외한 다음 연결리스트를 연결해주는 과정에서도 swap 과정이 필요하기 때문에, 해당 부분에 대해서도 swap 함수를 부른 결과를 다음 노드로 저장
4. 최종 바뀐 순서의 첫 번째 노드를 반환

 문제에서 요구하는 부분은 주어진 연결리스트에서 두 노드씩 순서를 바꾸는 것으로, 단순히 2개를 꺼내 바꾸면 될 것 같지만, 그 다음 연결리스트를 연결하는 과정에서 그 다음 노드들도 순서가 바뀌어 있어야 하기에 일종의 재귀를 통한 연쇄적 변환이 필요하다.

 결국 연결리스트 속 2개의 노드를 바꿔주는 swap 함수를 만들어주면서, 이를 일종의 재귀함수 형식으로 만들어준다. 파라미터로는 ListNode를 받으며, 들어온 ListNode가 null이거나 ListNode의 다음 노드가 없다면 순서를 바꿀 필요가 없으므로 그대로 반환해준다. 그 이후엔 순서대로 2개의 노드를 뽑은 다음 순서를 바꿔주는데, 기존 두 번째 노드의 다음으로는 첫 번째를 연결해주면 되지만 기존 첫 번째 노드의 다음으로는 다음 연결리스트를 연결해주면서 동시에 그 연결리스트 속 노드들의 순서도 바뀌어져야 있어야 하기 때문에 swap함수를 부른 결과를 다음으로 저장해준다. 그 이후엔 해당 함수의 반환값으로 순서 바뀌고 나서의 첫 번째 노드, 즉 기존의 두 번째 노드를 반환해주면 된다.

 그리고 기존 swapParis 함수에서 swap 함수를 부르면서 인자로 해당 head를 넘긴 결과를 반환하면 된다.

 

class Solution {
    public ListNode swapPairs(ListNode head) {
        return swap(head);
    }

    ListNode swap(ListNode node) {
        if (node == null) {//null인 경우
            return null;
        }

        if (node.next == null) {//swap할 다음 노드가 없는 경우
            return node;
        }

        ListNode first = node, second = node.next;

        first.next = swap(second.next);//그 다음 노드들의 swap 결과
        second.next = first;//처음 노드

        return second;//바뀐 순서의 노드
    }
}

결과