[Leetcode]328: Odd Even Linked List

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

Problem : 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.
有一個單項 linklist 需要reorder，把所有奇數node按順序接在一起，偶數node按順序接在一起，然後奇數 linklist 放前面，偶數 linklist放後面接起來。

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.

圖來自leetcode

Thoughts :
1. 把奇數node接起來，linklist變成 1->3->5->7
2. 把偶數node接起來，linklist變成 2->4->6->8
3. 把奇數linklist跟偶數linklist接起來

Solution :

class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if not head:
            return None
        odd, even = head, head.next
        eventmp = even
        while even and even.next:
            # 1接到3
            odd.next = even.next
            # 1指標移到3
            odd = odd.next
            # 2接到4
            even.next = odd.next 
            # 2指標移到4
            even = even.next 
        # 1的最後一個指標接到2
        odd.next = eventmp
        return head

Time Complexity : O(n)
# one while loop -> n

Space Complexity : O(1)
每次執行都執行都建立一樣的個數的變數，也就是說每次執行都是耗費一樣的記憶體空間，所以是O(1)。