[자바 알고리즘 인터뷰] 8장 연결 리스트(5) - 페어의 노드 스왑

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

 

 

- 연결 리스트를 입력받아 페어(pair)단위로 스왑하라 

 

 

풀이 1) 값만 교환 

 

- 연결 리스트의 노드를 변경하는 게 아닌, 노드 구조는 그대로 유지하되 값만 변경하는 방법 

 

class Solution {
    public ListNode swapPairs(ListNode head) {
        //스왑을 진행할 노드 선언
        ListNode node = head;

        //현재 노드와 다음 노드가 존재하면 계속 진행 
        while(node != null && node.next!=null)
        {
            //임시 변수를 이용해 값만 교환
            int tmp;
            tmp = node.val;
            node.val = node.next.val;
            node.next.val = tmp;

            //두칸 앞으로 이동
            node = node.next.next;
        }

        //첫 번째 노드를 정답으로 리턴 
        return head;
    }
}

 

 

풀이 2) 반복 구조로 스왑 

 

- 단순히 값을 바꾸는 일에 비해 연결 리스트 자체를 바꾸는 일은 다소 복잡한 문제 

- 1->2->3->4->5->6인 연결 리스트에서 3->4를 4->3으로 바꾼다고 할 때, 단순히 둘만 바꾼다고 끝나는 문제가 아니라 그 앞인 2가 가리키는 연결 리스트와 5로 연결되는 연결 리스트도 다 같이 변경해야 하기 때문 

 

- 현재 노드를 node, 다음 노드를 a, 다음 다음 노드를 b라고 할 때 다음과 같이 변경할 수 있다. 

a.next = b.next;
node.next = b;
node.next.next = a;

 

- node->a->b-> 구조 였던 연결 리스트가 ->node->b->a 구조로 변경 

- 이렇게 위치를 변경한 이후에는 두 칸씩 앞으로 이동하며 다시 다음번 교환을 진행하면 됨 

 

class Solution {
    public ListNode swapPairs(ListNode head) {
        //값을 계산할 임시 노드 선언
        ListNode node = new ListNode(0);

        //임시 노드를 첫 번째 노드로 선언
        ListNode root = node;

        //다음 노드는 첫 번째 노드로 지정
        node.next = head;

        //다음 노드와 다음 다음 노드가 있으면 반복
        while(node.next!= null && node.next.next!= null)
        {
            //a는 다음 노드 
            ListNode a = node.next;
            //b는 다음 다음 노드 
            ListNode b = node.next.next;

            //위치 변경
            a.next = b.next;
            node.next = b;
            node.next.next = a;

            //두 칸 앞으로 이동
            node = node.next.next;
        }

        //첫 번째 노드는 임시 노드이므로 그 다음부터 결과로 리턴
        return root.next;
    }
}

 

 

풀이 3) 재귀 구조로 스왑 

 

- 반복 풀이와 달리 포인터 역할을 하는 p 변수는 하나만 있어도 충분하며, 더미 노드를 만들 필요 없이 head를 바로 리턴할 수 있어 공간 복잡도가 낮다. 

- p는 head.next가 되고, p.next는 head가 된다. 

- 물론 그 사이에 재귀 호출로 계속 스왑된 값을 리턴받게 된다. 

- 다른 연결 리스트 문제들의 풀이와 마찬가지로 실제로는 리턴되면서 연결 리스트가 이어지게 된다. 

 

출처 : 자바 알고리즘 인터뷰 with 코틀린 저자 : 박상길 <책만>

 

class Solution {
    public ListNode swapPairs(ListNode head) {
        //현재 노드와 다음 노드가 있으면 반복
        if(head!=null && head.next!=null)
        {
            //다음 노드 선언
            ListNode p = head.next;
            //다음 다음 노드를 파라미터로 전달하고 스왑된 값을 리턴받음
            head.next = swapPairs(head.next.next);
            //다음 다음 노드는 현재 노드로 지정
            p.next = head;
            //다음 노드 리턴
            return p;
        }

        return head;
    }
}