328. Odd Even Linked List

짝수 번째 노드들을 뒤로 보내야한다.

Solution

1. 홀수 번째와 짝수 번째 head와 tail을 사용한다.
2. 짝수 번째 노드와 그 다음 노드(홀수 번째)가 존재하지 않을 때까지 while문을 돌린다.
   2.1. 홀수 번째 노드를 다음 홀수 번째 노드와 연결한다.
   2.2. 짝수 번째 노드를 다음 짝수 번째 노드와 연결한다.
3. 홀수 번째 노드들의 꼬리에 짝수 번째 노드들의 head를 연결한다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        # odd/even번째 헤드 테일 분리
        odd_head = head
        even_head = head.next
        odd_tail = odd_head
        even_tail = even_head

        while even_tail and even_tail.next:
            odd_tail.next = even_tail.next # 1->3
            odd_tail = odd_tail.next # 3 홀수 번째 노드를 다음 홀수 번째 노드와 연결
            even_tail.next = odd_tail.next # 2->4
            even_tail = even_tail.next # 4 짝수 번째 노드를 다음 짝수 번째 노드와 연결
        
        odd_tail.next = even_head # 홀수 꼬리에 짝수 head 연결 : 홀수 번째들->짝수 번째들
        return odd_head

cur.next = cur.next.next
처음에는 코드를 이렇게 작성했었는데... 이런 식의 꼼수는 안 되는구나.

시간 복잡도

모든 노드를 다 돌지만 한 번에 두 번 넘어가니 노드의 개수가 n이면 n/2 만큼 반복하는 것이다. 그러므로 시간 복잡도는 O(n/2) 이다.