# 328 odd even linked list

### 328. Odd Even Linked List

Medium


class Solution(object):
"""
:rtype: ListNode
"""

oddDummy = ListNode(-1)

evenDummy = ListNode(-1)

oddCur = oddDummy.next
evenCur = evenDummy.next

while cur:
oddCur.next = cur
oddCur = oddCur.next
evenCur.next = cur.next
evenCur = evenCur.next
if cur.next:
cur = cur.next.next
else:
cur = cur.next
oddCur.next = evenDummy.next
# print oddDummy.next.val
return oddDummy.next



class Solution(object):
"""
:rtype: ListNode
"""

# odd used to keep track of the tail of odd nodes
# record how many swaps happend
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next


intuitive and concise

1 → 2 → 3 → 4 → 5 → NULL

1    → 2     → 3 →    4    → 5    → NULL
odd   even     even.next

1 → 3  →    4    → 5    → NULL
odd     ↑
2   -

1 → 3  →    4    → 5    → NULL
odd
2   -   even

|   -----------
|   ---------  ↓       ↓
1 → 3       4      5    → NULL
odd       ↑
2   -   ↑              even



apachecn/AiLearning