328. Odd Even Linked List
給你一個 linked list，要你重排裡面的 node
先排原本奇數位的那些 node，後面再接上原本偶數位的那些 node
題目另外要求 O(1) extra space
Example:
Example 1:
https://assets.leetcode.com/uploads/2021/03/10/oddeven-linked-list.jpg
Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]
奇數位 1 3 5 -> 偶數位 2 4
Example 2:
https://assets.leetcode.com/uploads/2021/03/10/oddeven2-linked-list.jpg
Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]
奇數位 2 3 6 7 -> 偶數位 1 5 4
思路:
1.可以分開串奇數位的 node 和 偶數位的 node， 最後再把奇數位尾串上偶數位頭
因為兩者在串的時候互不相干所以可以從頭掃 linked list 一次建完
每次記住兩個 node: odd 跟 even，代表奇數位和偶數位
然後 odd.next = odd.next.next, even.next = even.next.next
假設原本是 1->2->3->4 就會讓 1->2 的箭頭變成 1->3， 2->3 的箭頭變成 2->4
接著再 odd = odd.next, even = even.next
odd, even 就會從原本的 1, 2 變成 3, 4
2.可以分析一下迴圈結束條件要怎麼設
如果 linked list 長度是偶數:
最後會變成 odd -> even -> null，這種狀況因為找到最尾巴的 odd 所以可以直接停
如果 linked list 長度是奇數:
最後會變成 odd -> null，這種狀況也是找到最尾巴了可以停
所以遇到 even == null or even.next == null 就可以結束了
最後再把 odd 接上事先存好的 even head 就好
Python code:
# 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: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return head
odd, even, evenhead = head, head.next, head.next
while even and even.next:
odd.next = odd.next.next
even.next = even.next.next
odd = odd.next
even = even.next
odd.next = evenhead
return head