LeetCode: 92번 (Reverse Linked List II) [JAVA]

문제 링크

https://leetcode.com/problems/reverse-linked-list-ii/

Reverse Linked List II - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. left == right라면, 받은 head를 반환
2. 현재 받은 리스트 헤더(head) 앞에 임시 헤더를 추가
3. 임시 헤더부터 시작하여 리스트 끝까지, 다음에 따라 노드를 처리
   1) 해당 노드의 순서가 left 직전이라면, 해당 노드를 따로 저장
   2) 해당 노드의 순서가 left~right 구간이라면, 해당 노드 값을 복사해 임시헤더를 만든 다음, 순서를 뒤집은 리스트에 추가
   이 때 순서가 left라면 추가로 해당 노드를 따로 저장하고, 순서가 right라면 left 직전 노드에 현재 뒤집은 리스트의 헤더를 추가하고, 뒤집은 리스트 노드 마지막에 right 다음 노드를 추가하는 과정을 진행
   
4. 임시헤더의 다음 노드를 반환

 주어진 리스트에서, left ~ right 까지의 구간을 뒤집어야 한다. 이를 해결하기 위해 노드들의 순서를 기억하고 뒤집는 작업을 시행해도 되지만, 좀 더 쉽게 문제를 해결하기 위해서 해당 뒤집는 구간동안 노드들의 값만 복사해 뒤집은 리스트를 새로 생성하기로 했다.
 이를 위해 우선 주어진 head 앞에, 임시적으로 붙일 임시 헤더를 생성한다. 그 다음 임시 헤더부터 리스트 끝까지 규칙에 따라 노드를 처리한다. 만약 노드가 left 직전의 노드라면, 이를 추후 작업을 위해 따로 저장한다. 노드가 left ~ right 구간에 속하는 노드라면, 해당 노드의 값을 복사한 새로운 노드를 생성한 다음, 순서를 뒤집은 노드 리스트에 이를 추가한다. 추가로 해당 노드가 left 순서라면 새로 복사한 노드를 따로 저장한다. 해당 노드가 right 순서라면, 여태까지 생성한 뒤집은 노드 리스트를 left 직전 노드의 다음으로 붙이고, 뒤집은 노드 리스트의 마지막의 다음으로 right 다음 노드를 지정한다.
 이후 해당 탐색이 끝나고, 임시 헤더의 다음 노드를 반환하면 된다.

 

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == right) {//바꿔야할 부분의 위치가 동일하다면 그대로 반환
            return head;
        }

        ListNode tempHead = new ListNode(-1, head); //리스트 앞단의 임시 헤더 추가
        ListNode temp = tempHead, previousReverseStart = null;
        ListNode reverseListHead = null, reverseStart = null;
        int positionCount = 0;

        while (temp != null) {
            if (positionCount == left - 1) {//바꿀 부분의 직전 노드를 따로 저장
                previousReverseStart = temp;
            }

            if (left <= positionCount && positionCount <= right) {//바꿔야할 구간
                ListNode copyNode = new ListNode(temp.val);
                copyNode.next = reverseListHead;
                reverseListHead = copyNode;

                if (positionCount == left) {//구간의 시작 노드는 따로 저장
                    reverseStart = reverseListHead;
                }

                if (positionCount == right) {//구간의 끝 노드 도착시 뒤집은 리스트를 이어붙이는 작업 진행
                    previousReverseStart.next = reverseListHead;
                    reverseStart.next = temp.next;
                    break;
                }
            }

            ++positionCount;
            temp = temp.next;
        }

        return tempHead.next;
    }
}

결과