328. Odd Even Linked List

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

solution

• 双指针

class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return head
        
        odd = head
        even = head.next
        init_even_head = even  # record the initial even

        while even and even.next:  # 一下跨两步
            odd.next = even.next
            odd = odd.next
            even.next = odd.next
            even = even.next
        odd.next = init_even_head
        return head

时间复杂度：O(n) 空间复杂度：O(1)

• 两段链表拼接

class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return head
        
        dummy_odd = odd = ListNode(0, head)
        dummy_even = even = ListNode(0, head.next)

        while even and odd and odd.next:
            if odd.next:
                odd.next = odd.next.next
            if even.next:
                even.next = even.next.next
            
            odd = odd.next
            even = even.next
       
        odd.next = dummy_even.next
        return dummy_odd.next