328. Odd Even Linked List(经典)

# Medium

非常锻炼LinkList基本功的一道题，要设置3个head，一个odd, 一个even，这两个指针都是动态的，还有一个evenHead，最后返回head，head一直不动

Key iead: even 的下一个是odd的下一个，even 的下下一个才是even的下一个

# 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:
        # edge case
        if head == None or head.next == None:
            return head

        odd = head
        even = head.next
        evenHead = even
        
        while even != None and even.next != None:
            odd.next = even.next
            odd = odd.next
            even.next = even.next.next
            even = even.next
        
        odd.next = evenHead
        return head

Time = $O(n)$ , Space = $O(1)$

Python中初始化一个Node时，无需odd=ListNode(None), odd=head, 而是直接 odd=head