145일 (2074. Reverse Nodes in Even Length Groups) LinkedList, 정말 어려움

You are given the head of a linked list.

The nodes in the linked list are sequentially assigned to non-empty groups whose lengths form the sequence of the natural numbers (1, 2, 3, 4, ...). The length of a group is the number of nodes assigned to it. In other words,

• The 1st node is assigned to the first group.
• The 2nd and the 3rd nodes are assigned to the second group.
• The 4th, 5th, and 6th nodes are assigned to the third group, and so on.

Note that the length of the last group may be less than or equal to 1 + the length of the second to last group.

Reverse the nodes in each group with an even length, and return the head of the modified linked list.

 

Example 1:

 

Input: head = [5,2,6,3,9,1,7,3,8,4]
Output: [5,6,2,3,9,1,4,8,3,7]
Explanation:
- The length of the first group is 1, which is odd, hence no reversal occurs.
- The length of the second group is 2, which is even, hence the nodes are reversed.
- The length of the third group is 3, which is odd, hence no reversal occurs.
- The length of the last group is 4, which is even, hence the nodes are reversed.

Example 2:

Input: head = [1,1,0,6]
Output: [1,0,1,6]
Explanation:
- The length of the first group is 1. No reversal occurs.
- The length of the second group is 2. The nodes are reversed.
- The length of the last group is 1. No reversal occurs.

Example 3:

Input: head = [1,1,0,6,5]
Output: [1,0,1,5,6]
Explanation:
- The length of the first group is 1. No reversal occurs.
- The length of the second group is 2. The nodes are reversed.
- The length of the last group is 2. The nodes are reversed.

 

Constraints:

• The number of nodes in the list is in the range [1, 10^5].
• 0 <= Node.val <= 10^5

 

- 접근방법

 

더 나은 방법을 찾기위해 몇시간 내내 고민하였다... 생소한데다가 어렵기까지 했다.

 

현재 그룹 크기(currentGroupSize) 는 1부터 1씩 누적되서 증가한다.
currentGroupSize가 짝수거나, 현재그룹의 노드 개수가 짝수일때 현재 그룹의 노드들을 역순으로 수정한다.

(head.next == null 일수도 있으니까 현재그룹의 노드개수와 currentGroupSiz는 항상 동일하지는 않다.)

 

0. 연결리스트 내부를 수정하려면

(이전그룹의 마지막 노드 + 역순으로 재배열 된 연결리스트 시작노드와 끝 노드 +다음에 시작될 노드) 가 필요하다.

 

1. getGroupEndNode() 메서드는 현재 그룹의 마지막 노드를 리턴한다.

( currentGroupSize에 속하는 마지막 노드거나 혹은 node.next == null인 마지막 노드거나)

 

2. reverseGroup() 메서드는 역순으로 재배열 될 시작노드, 역순으로 재배열 될 노드의 개수를 매개변수로 하여 주어진 조건 내의 연결리스트를 역순으로 수정한다.

 

3. 현재그룹(currentGroupSize)에 속하는 노드들의 범위를 구한다. 

 

4. 현재그룹(currentGroupSize)에 속하는 노드의 개수가 짝수라면,  이전그룹의 마지막 노드(prevNode) + reversed[0](역순으로 뒤집힌 연결리스트의 시작노드) + reversed[1] (역순으로 뒤집힌 연결리스트의 마지막노드)를 연결한다.

 

5. 현재그룹(currentGroupSize)에 속하는 노드의 개수가 홀수라면,  이전 마지막 노드의 다음노드로 현재 그룹을 잇는다.

 

 

 

- 코드

class Solution {
    public ListNode reverseEvenLengthGroups(ListNode head) {
        ListNode answer = new ListNode(0, head);
        ListNode prevNode = answer;
        int currentGroupSize = 1;

        while (head != null) {
            ListNode currStartNode = head;
            int size = 0;

            while (head != null && size < currentGroupSize) { // 3
                head = head.next;
                size++;
            }

            if (size % 2 == 0) { // 4
                ListNode[] reversed = reverseGroup(currStartNode, size);
                prevNode.next = reversed[0];
                prevNode = reversed[1];
            } else {
                prevNode.next = currStartNode; // 5
                prevNode = head == null ? currStartNode : getGroupEndNode(currStartNode, size);
            }

            currentGroupSize++;
        }

        return answer.next;
    }

    private ListNode[] reverseGroup(ListNode head, int size) { // 2
        ListNode tempHead = head;
        ListNode startNode = null;
        ListNode endNode = head;
        int cnt = 0;

        while (cnt < size) {
            ListNode nextNode = tempHead.next;
            tempHead.next = startNode;
            startNode = tempHead;
            tempHead = nextNode;
            cnt++;
        }
        endNode.next = tempHead;
        return new ListNode[]{startNode, endNode};
    }

    private ListNode getGroupEndNode(ListNode start, int size) { // 1
        while (start != null && size > 1) {
            start = start.next;
            size--;
        }
        return start;
    }
}

 

 

노드가 짝수개수 그룹일때 직접 역순으로 수정하면 현재 그룹의 노드는 역순으로 수정되었는데, 가르키는 포인터는 역순으로 수정되기 이전 값을 가르킨다.

 

포인터명(startNode, endNode 등)으로 현재 그룹의 시작노드와 끝 노드를  포인터로 기억하기 보다는 배열에 수정된 후 시작노드, 끝노드를 기억하는 것이 좋다.

그리고 메모지에 손으로 수정 이전 포인터와 수정 후 포인터 위치도 작성하면서 확인해보고 헷갈림을 방지할 수 있다.

 

 

 

 

https://leetcode.com/problems/reverse-nodes-in-even-length-groups/

LeetCode - The World's Leading Online Programming Learning Platform