[LeetCode] 24. Swap Nodes in Pairs - 구현(Implementation) JAVA

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

코드설명

구현(Implementation) 입니다.

 

첫 풀이는, 매우 복잡하게 남은 노드가 홀수,짝수인지에 따라 따라 이동위치를 직접 변경시키는 방식으로 했습니다만, 해당 방식으로는 Reference 객체가 계속해서 뒤집어쓰이게 되는 방식이 있어서 주소 위치를 올바르게 수정시킬 수 없는 문제가 있었습니다.

 

솔루션을 접하고서 문제의 접근방법입니다.

1. dummy Node를 생성하여, 기존값에 영향을 주지않으면서 처리하기 훨씬 쉬워집니다.

2. Current Node Pair와 Next Pair Node로 가장 근처의 것을 서로 Swap 하여 연결하여야하니, Current Node Pair에서는 Prev가 필요하고, Next Pair Node에서는 current Node Pair에서 연결해야할 주소위치가 되어야 하니, 한쌍으로 묶는것을 생각하여 처리합니다. (만약 Pairs가 안만들어진다면, 즉 cur != null && cur.next != null 이라면 홀수인경우는 바로 종료시키면 됩니다.)

3. 해당 작업을 반복합니다.

코드

정답코드 1입니다.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy;
        ListNode cur = head;

        while(cur != null && cur.next != null){
            ListNode nextPairNode = cur.next.next;
            ListNode second = cur.next;
            second.next = cur;
            cur.next = nextPairNode;
            prev.next = second;

            prev = cur;
            cur = nextPairNode;
        }

        return dummy.next;
        
    }
}