328. Odd Even Linked List

문제

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.

접근

#연결리스트

홀수 번째 노드와 짝수 번째 노드를 따로 저장하여, 모든 순회가 끝난 뒤 이어붙이도록 한다. 자세한 사항은 코드의 주석을 참고한다.

코드

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def oddEvenList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return head
        
        odd = head # 홀수 번째 노드를 모으는 리스트
        even = head.next # 짝수번째 노드를 모으는 리스트
        eHead = even # 마지막에 odd 뒤에 붙일 첫 번째 even의 주소
        
        while even and even.next:
        # even이 더 뒤에 위치하므로 even이 None이 아닌 범위 내에서만 반복한다.
        
            odd.next = odd.next.next
            even.next = even.next.next
            # 각 홀수/짝수 리스트의 next를 다음 홀수/짝수로 둔다.
            # 홀수 짝수를 한 덩어리로 묶어 진행하는 개념.
        
            odd = odd.next
            even = even.next
        
        odd.next = eHead # 홀수 리스트의 뒤에 짝수 리스트를 붙인다.
        
        return head 

효율성

https://leetcode.com/problems/odd-even-linked-list/submissions/855384513/