연결 리스트 전체를 역순으로 변환하기

문제 설명

단일 연결 리스트의 머리 노드 head가 주어졌을 때, 이를 역순으로 변환하고 변환된 연결 리스트를 반환하세요.

예시1: 생략 예시2: 생략

해결 방법

방법 1: 순차 처리

연결 리스트가 1→2→3→∅라고 가정해보겠습니다. 우리가 원하는 결과는 ∅←1←2←3입니다. 각 노드를 순회하면서 해당 노드의 다음(next) 포인터를 이전(prev) 노드로 변경하면 됩니다. 하지만 단방향 연결 리스트에서는 현재 노드에서 이전 노드에 접근할 수 없으므로, 별도의 prev 변수를 사용해야 합니다.

아래와 같은 순차적 단계를 수행합니다:

• 현재 노드(curr)의 다음(next) 노드를 임시 저장
• 현재 노드의 next를 prev로 설정
• prev를 현재 노드로 갱신
• curr를 다음 노드로 이동

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode current = head;
        ListNode previous = null;

        while (current != null) {
            ListNode tempNext = current.next;
            current.next = previous;
            previous = current;
            current = tempNext;
        }

        return previous;
    }
}

복잡도 분석 시간 복잡도: O(N), 한 번만 순회함 공간 볤잡도: O(1)

방법 2: 재귀적 접근

다음과 같이 연결 리스트를 가정합시다:

n1→…→n**k−1→n**k→n**k+1→…→n**m→∅

노드 n**k+1부터 n**m까지 이미 역순으로 변환이 완료되었다고 가정합니다:

n1→…→n**k−1→n**k→n**k+1←…←n**m

이제 n**k+1의 다음 노드를 n**k로 설정해야 합니다. 따라서 다음과 같이 코드를 작성할 수 있습니다:

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;

        return newHead;
    }
}

복잡도 분석 시간 복잡도: O(N) 공간 복잡도: O(N), 재귀 호출 스택 사용

특정 구간의 연결 리스트 역순 변환

문제 설명

단일 연결 리스트의 머리 노드 head와 두 개의 정수 left, right가 주어졌을 때(left <= right), 위치 left부터 right까지의 노드들을 역순으로 변환한 후 연결 리스트를 반환하세요.

예시1:

입력: head = [1,2,3,4,5], left = 2, right = 4
출력: [1,4,3,2,5]

예시2:

입력: head = [5], left = 1, right = 1
출력: [5]

해결 방법

방법 1: 단일 스캔

연결 리스트를 세 부분(왼쪽, 중간, 오른쪽)으로 나누고, 중간 부분을 역순으로 변환한 뒤 다시 세 부분을 연결합니다.

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(0, head);

        // 1. 왼쪽 부분의 마지막 노드 찾기
        ListNode node = dummy;
        for (int i = 1; i < left; i++) {
            node = node.next;
        }
        ListNode leftTail = node;

        // 2. 중간 부분 역순 변환
        node = node.next;
        ListNode midHead = node;
        ListNode prev = null;
        for (int i = left; i <= right; i++) {
            ListNode tempNext = node.next;
            node.next = prev;
            prev = node;
            node = tempNext;
        }

        // 3. 다시 연결
        leftTail.next = prev;
        midHead.next = node;

        return dummy.next;
    }
}

방법 2: 연결 조작 기법

pre는 항상 왼쪽 부분의 마지막 노드를 가리키며, curr은 항상 오른쪽 부분의 첫 번째 노드를 가리킵니다. 반복마다 아래 작업을 수행합니다:

• curr의 다음 노드를 임시 저장
• curr의 다음 노드를 조정
• 임시 노드를 적절히 연결

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;

        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }

        ListNode cur = pre.next;
        ListNode next;
        for (int i = 0; i < right - left; i++) {
            next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }

        return dummyNode.next;
    }
}

K개씩 그룹화하여 역순 변환

문제 설명

연결 리스트의 머리 노드 head가 주어졌을 때, K개의 노드를 하나의 그룹으로 묶어서 그룹 내부를 역순으로 변환하고, 수정된 연결 리스트를 반환하세요.

예시1:

입력: head = [1,2,3,4,5], k = 2
출력: [2,1,4,3,5]

예시2:

입력: head = [1,2,3,4,5], k = 3
출력: [3,2,1,4,5]

해결 방법

방법 1: 시뮬레이션

먼저 K개의 노드가 남아있는지 확인하고, 만약 K개 미만이라면 변환하지 않고 그대로 반환합니다. K개 이상이라면 해당 그룹을 역순으로 변환한 뒤, 원래 연결 리스트에 다시 연결합니다.

class Solution {
    public ListNode reverseKGroup(ListNode list, int k) {
        ListNode dummy = new ListNode(0, list);
        ListNode tail = dummy;

        while (true) {
            ListNode current = tail;
            for (int i = 0; i < k; i++) {
                current = current.next;
                if (current == null) {
                    return dummy.next;
                }
            }

            ListNode nextGroupHead = current.next;
            ListNode currentGroupHead = tail.next;
            ListNode prev = nextGroupHead;
            current = tail.next;

            while (current != nextGroupHead) {
                ListNode tempNext = current.next;
                current.next = prev;
                prev = current;
                current = tempNext;
            }

            tail.next = prev;
            tail = currentGroupHead;
        }
    }
}