leetcode link

Description

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.

---

주어진 단일 연결 리스트의 head가 있을 때, 모든 홀수 인덱스의 노드만 모으고 그 뒤에 짝수 인덱스의 노드만 모아 붙여 재정렬된 리스트를 반환합니다.

첫 번째 노드는 홀수로 간주되며, 두 번째 노드는 짝수로 간주되며, 이런 식으로 계속됩니다.

홀수 그룹과 짝수 그룹 내의 상대적 순서는 입력에서와 같아야 한다는 점에 유의하세요.

문제는 O(1)의 추가 공간 복잡도와 O(n)의 시간 복잡도로 해결해야 합니다.

예시 1:

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

예시 2:

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

제약사항:

• 연결 리스트의 노드 수는 [0, 10^4] 범위에 있습니다.
• -10^6 <= Node.val <= 10^6

Solution

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode odd = head, even = head.next, evenHead = head.next;

        while (even != null && even.next != null) {
            odd.next = odd.next.next;
            odd = odd.next;
            even.next = even.next.next;
            even = even.next;
        }

        odd.next = evenHead;
        return head;
    }
}