[코딩테스트 - Java] 연결 리스트 활용

연결 리스트에 대한 문제를 포스팅하겠다.

24. Swap Nodes in Pairs

인접 노드들을 쌍으로 스왑하는 문제이다.
아래의 예시에서 간단하게 설명한다.

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

하나만 남거나 비어있는 종료 조건의 경우 예외 처리는 어렵지 않았다. 다만, 현재 가리키는 노드가 바뀌면서 기존 리스트에 적용시키는 부분을 애먹었다.

class Solution {
    public ListNode swapPairs(ListNode head) {
    	// 초기 노드 설정
        ListNode dump = new ListNode(0);
        dump.next = head;
        ListNode current = dump;
		
        // 종료 조건
        while(current.next != null && current.next.next != null){
            current = swap(current);
        }

        return dump.next;
    }

    public ListNode swap(ListNode current){
        ListNode fstNode = current.next;
        ListNode secNode = current.next.next;
		
        // swap 시작
        fstNode.next = secNode.next;
        secNode.next = fstNode;
        // current에 적용
        current.next = secNode;
		// current의 위치를 리스트의 가장 끝으로 옮기기
        current = fstNode;
        
        return current;
    };
}

연결 리스트 문제를 풀 때마다 dummy 노드를 초기에 설정하는 것이 가장 편하게 문제를 풀 수 있는 방법인 것 같다.

25. Reverse Nodes in k-Group

주어진 연결 리스트를 k개 만큼 뒤집는 것을 반복하는 문제이다. 남은 개수가 k개 미만이면 그대로 연결해준다.

이전에 풀었던 문제와 유사하지만, 정렬이 아니라 뒤집는 것이 차이점이다.

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

이전에 Priority Queue를 사용했던 문제가 기억나서 LIFO(후입선출) 방식인 Stack을 활용하여 풀었다.

예외처리는 stack이 비었을 때의 노드를 저장해놓고 stack이 남아있을 시에 연결해버리도록 하였다.

import java.util.*;

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // node를 넣어둘 스택을 생성
        Stack<ListNode> stack = new Stack<>();
        // return할 dump node 생성
        ListNode dump = new ListNode(0);
        ListNode current = dump;
        // 뒤집을 노드들 중의 첫번째
        ListNode fst = current;
        // 리스트의 끝까지 순회
        while(head != null){
            if(stack.size() < k){
                // 첫번째 노드이면 fst에 기록
                if(stack.isEmpty()){
                    fst = head;
                }
                // 스택에 추가 및 head 이동
                stack.push(head);
                head = head.next;
            }
            // stack 길이가 k이면 비우기
            if(stack.size() == k){
                while(!stack.isEmpty()){
                    // 위에서부터 노드에 연결
                    current.next = stack.pop();
                    current = current.next;
                    current.next = null;
                }
            }
        }
        // stack이 남아있다면 current의 끝에 fst 연결
        if(!stack.isEmpty()){
            current.next = fst;
        }
        
        return dump.next;
    }
}

해당 코드는 4ms / 44.23mb 으로 성능 상 아쉬운 부분이 생긴다.
이유는 stack을 비울 때 while문 내에 이미 방문한 노드에 대한 연산을 다시 수행하기 때문인 것 같다.

성능 향상을 위해서는 주어진 노드들을 방문하면서 함께 연산하는 것이 중요해보인다. 아래는 chatGpt가 제공한 코드를 참고했다.

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prevGroupEnd = dummy;

        while (true) {
            // k개 노드가 있는지 확인
            ListNode kth = getKthNode(prevGroupEnd, k);
            if (kth == null) break;

            ListNode groupStart = prevGroupEnd.next;
            ListNode nextGroupStart = kth.next;

            // reverse group
            ListNode prev = kth.next;
            ListNode curr = groupStart;
            while (curr != nextGroupStart) {
                ListNode tmp = curr.next;
                curr.next = prev;
                prev = curr;
                curr = tmp;
            }

            // 그룹 이전 노드와 연결
            prevGroupEnd.next = kth;
            prevGroupEnd = groupStart;
        }

        return dummy.next;
    }

    private ListNode getKthNode(ListNode start, int k) {
        while (start != null && k > 0) {
            start = start.next;
            k--;
        }
        return start;
    }
}