# LeetCode Medium 328. Odd Even Linked List

tags: leetcode

問題

• Explore
• Problems

アイデア

｢与えられた単方向連結リストの奇数番目のノード群から繋げて，偶数番目のノード群を繋げろ｣という問題です．つまり1->2->3->4->5->NULLを1->3->5->2->4にしろということです(1-indexed)．

更にin-place，つまり空間計算量$O(1)$で実装する必要があります．また，ノードの元々の順番を考慮して奇数番目，偶数番目のノードを繋げる必要が有ります．

解法

• 奇数と偶数のノードを指す変数を用意します．
• これらを付け替えます．

計算量

単方向連結リストのノードを$N$をとします．

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(1)$

Python

# 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: ListNode) -> ListNode:
        if not head:
            return head
        odd = head
        even = head.next
        even_head = even
        while even and even.next:
            odd.next = odd = even.next
            even.next = even = odd.next
        odd.next = even_head
        return head