328. Odd Even Linked List

Odd Even Linked List - LeetCode

 

단일 연결 리스트의 헤드가 주어졌을 때, 홀수 인덱스 노드를 모두 모아서 그 다음에 짝수 인덱스 노드를 따르도록 리스트를 재정렬하고 결과 리스트를 반환하세요. 첫 번째 노드는 홀수로 간주되고, 두 번째 노드는 짝수로 간주되며, 이러한 순서로 계속됩니다. 홀수 그룹 및 짝수 그룹 내부에서의 상대적인 순서는 입력과 동일하게 유지되어야 합니다.

 

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

The first node is considered odd, and the second node is even, and so on.

Note that the relative order inside both the even and odd groups should remain as it was in the input.

You must solve the problem in O(1) extra space complexity and O(n) time complexity.

 

Example 1:

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

Example 2:

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

 

풀이과정 설명:

1. 홀수 노드와 짝수 노드를 나누어야 합니다.
2. 각 그룹의 마지막 노드를 추적하여 나중에 결합할 수 있도록 합니다.
3. 홀수 그룹의 마지막 노드의 next를 짝수 그룹의 첫 번째 노드로 연결합니다.
4. 원래 리스트의 끝에 도달하면 홀수 그룹의 마지막 노드의 next를 짝수 그룹의 첫 번째 노드로 설정하고 반환합니다.

/**
 * 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 oddEvenList(ListNode head) {
        ListNode oddNode = head;
        ListNode evenNode = head.next;
        ListNode evenTopNode = evenNode;

        while(evenNode != null && evenNode.next != null){
            oddNode.next = evenNode.next;
            oddNode = oddNode.next;
            
            evenNode.next = oddNode.next;
            evenNode = evenNode.next;
        }
        oddNode.next = evenTopNode;
        
        return head;
    }
}