24. Swap Nodes in Pairs

문제

주어진 연결 리스트에서 인접한 두 노드씩 교환한 후, 변경된 리스트의 헤드를 반환하라. 단, 노드의 값을 직접 바꾸면 안 되고, 노드 자체를 교환해야한다.

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을 할 때에는 꼭 이전 변수의 값을 미리 담아둘 임시 변수가 필요하다는 것을 기억해두면 좋을 것 같습니다.