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