Odd Even Linked List ใน Python

จัดกลุ่มโหนดตำแหน่งคี่ (odd) ไว้หน้า ตามด้วยตำแหน่งคู่ (even) ใน singly linked list โดยทำ in-place

ตัวอย่าง

Input:  1 → 22 → 13 → 14 → 25
Output: 1 → 13 → 25 → 22 → 14

แนวคิด

• ใช้ pointer สองตัว: odd และ even
• แยก list เป็นสองสาย แล้วต่อท้าย odd เข้ากับ head ของ even

โค้ด

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def oddEvenList(self, head):
        if not head or not head.next:
            return head
        
        odd = head
        even = head.next
        even_head = even
        
        while even and even.next:
            odd.next = even.next
            odd = odd.next
            even.next = odd.next
            even = even.next
        
        odd.next = even_head
        return head

# Helper สำหรับทดสอบ
def make_list(vals):
    head = ListNode(vals[0])
    cur = head
    for v in vals[1:]:
        cur.next = ListNode(v)
        cur = cur.next
    return head

def print_list(head):
    res = []
    while head:
        res.append(str(head.val))
        head = head.next
    print(" → ".join(res))

# ทดสอบ
head = make_list([1, 22, 13, 14, 25])
sol = Solution()
print_list(sol.oddEvenList(head))

ผลลัพธ์

1 → 13 → 25 → 22 → 14

สรุป

วิธี two-pointer แยก odd/even แล้วต่อกัน ได้ O(n) time, O(1) space