[문제풀이] 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.)

입출력 예시:

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

✨ 풀이

/**
 * 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 prevNode = new ListNode(0); 
        // 더미 노드 생성 -> [0,1,2,3,4]
        prevNode.next = head; 
        // 더미 뒤부터 시작한다는 의미
        ListNode newHead = prevNode;
        // 리턴할 노드
        
        while(prevNode.next!=null && prevNode.next.next!=null){
            
            // 순서: [prevNode]->[node1]->[node2]->[next]...
            ListNode node1 = prevNode.next;                     
            ListNode node2 = node1.next;
            ListNode nextNode = node2.next;
            
            //스왑
            prevNode.next = node2; 
            // [prevNode]-[node2]<-[node1]-[next]...
            // node1, 2 서로 자리를 바꿨다기보다 node1의 위치에 node2를 데려간 것
            node2.next = node1;
            // [prevNode]-[node2]->[node1]-[next]...
            // node1을 2의 자리로 데려간 것
            node1.next = nextNode;
            // [prevNode]->[node2]->[node1]->[next]...
            // 한 쌍 자리 바꾸기 완료 후, node1 기준 다음 칸이 nextNode
            
            // 다음 쌍으로 옮겨가기
            // [이전 쌍의 두번째 노드 node1]-[다음 쌍...]
            // node1이 유사 더미 역할 수행
            prevNode = node1;
            
        }
        
        return newHead.next;
    }

풀이 노트:

• 리스트노드 문제풀이에 (거의) 필수인 더미 노드를 우선 생성한다.
• 리스트노드이기 때문에 배열처럼 길이를 구해서 풀 수 없다. (때문에 하나씩 읽으며 재귀로 풀이)
• 한 쌍을 단위로 바꿔줘야 하기 때문에 포인터가 두 개 필요하다.
• ListNode 감을 좀 잡았다 싶었는데... 이 문제를 하루종일 고민한 것 같다. 포인트 두 개가 필요한 것과 더미 노드를 활용해야 한다는 건 알겠는데 어떻게 값을 수정하지 않으며 할당하고, 다음 쌍으로 옮겨갈지 곧바로 떠오르지가 않았다. 변수를 생성해서 값을 할당하는 게 아니라 .next로 오목 두듯이 앞에 붙였다 뒤에 붙였다 해야 해서 그림을 그리며 푸는 게 확실히 도움됐다.
• 다양한 풀이를 참고했는데 두 포인터와 .next로 스왑해주는 건 대부분 동일하다.
• 이 알고리즘의 중요도가 어떻게 되는지 모르겠으나 아리까리한 게 싫어서 한동안 집중 공략해야겠다...^^