题解 | #链表的奇偶重排#

线性扫描链表

1. 当前为奇数时，加入奇数链表odd
2. 当前为偶数时，加入偶数链表
3. 将偶数的最后一个节点断开，避免构成环导致无限循环

class Solution:
    def oddEvenList(self , head ):
        # write code here
        if head is None or head.next is None:
            return head
        odd = ListNode(0)
        even = ListNode(0)
        o = odd
        e = even
        p = head
        flag = 1
        while p:
            if flag == 1:
                o.next = p
                o = o.next
            else:
                e.next = p
                e = e.next
            p = p.next
            flag *= -1
        o.next = even.next
        e.next = None
        return odd.next