LeetCode 24. Swap Nodes in Pairs, 페어의 노드 스왑

문제(링크):

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

 

Example 1:

 

Example 2:

Input: head = [1,2,3,4]
Output: [2,1,4,3]

 

Example 3:

Input: head = []
Output: []

 

 

---

문제 풀이:

 

1 → 2 → 3 → 4 → 5 → 6 인 연결 리스트에서 3 → 4를 4 → 3 으로 바꾼다고 할 때, 그 앞 1 이 가리키는 node와 뒤의 노드 6으로 연결하는것 까지 작업해야 한다.

 

 ListNode의 순서는 다음과 같은 PASS를 거치게 된다.

PASS 0: 1 → 2 → 3 → 4 → 5 → 6
PASS 1: 2 → 1 → 3 → 4 → 5 → 6
PASS 2: 2 → 1 → 4 → 3 → 5 → 6
PASS 3: 2 → 1 → 4 → 3 → 6 → 5

아래와 같은 순서로 작업이 진행되며, 진행이 완료되면 반복된다.

1. 0번 노드는 2번 노드를 바라본다.
2. 2번 노드는 1번 노드를 바라본다.
3. 1번 노드는 3번 노드를 바라본다.
4. 0번 노드 기준점을 1번 노드로 변경한다. 위 작업을 반복한다.

위 설명을 그림으로 확인하면 아래와 같다.

풀이 코드는 아래와 같다.

    // ListNode 순서 수정
    public ListNode swapPairsB(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return head;
        // head Node와 그 다음 node가 교환되므로 next가 root가 됨.
        ListNode root = head.next;
        // node의 첫번째 교환을 위한 임시 노드를 생성. 이후 해당 node는 포인터와 같은 역할을 함
        ListNode node = new ListNode(0);
        // 임시 노드에 매개변수로 주어진 head 노드를 이어붙임
        node.next = head;

        while (node.next != null && node.next.next != null) {
            // {{1}, {2}} 두 노드를 서로 교환해야 함. 교환 후 {{2}, {1}}과 같이 돼야 한다
            ListNode leftNode = node.next;
            ListNode rightNode = node.next.next;
            node.next = rightNode;
            leftNode.next = rightNode.next;
            rightNode.next = leftNode;

            node = node.next.next;
        }
        return root;
    }