給一個(gè)單鏈表，要求重新排序，前一半為鏈表的奇數(shù)位，后一半為偶數(shù)位，e.g.,
Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]
設(shè)置三個(gè)指針位置，odd表示當(dāng)前奇數(shù)位處理到哪里，r表示目前已處理到的位置的下一位，even表示當(dāng)前偶數(shù)位處理到哪里，另設(shè)置pos記錄當(dāng)前已經(jīng)處理過多少個(gè)（用于判斷奇偶）
1.如果當(dāng)前處理偶數(shù)位，odd指向r，r指向next，even不變，e.g.,
1->3->2->4->5->6->7 (此時(shí)odd指向3，even指向2，r指向4)
在處理節(jié)點(diǎn)4時(shí)，指針更新為：odd依舊指向3，even指向4，r指向5，鏈表順序不變
2.如果當(dāng)前處理奇數(shù)位，先用臨時(shí)變量記錄第一個(gè)偶數(shù)位（first_even = odd.next），r的下一位（r_next = r.next），然后分五步改變鏈表指針順序
1->3->2->4->5->6->7 (此時(shí)odd指向3，even指向4，r指向5)
s1：更新odd.next = r (讓3的下一位指向5)
s2：更新r.next = first_even (讓5的下一位指向2)
s3：更新even.next = r_next (讓4的下一位指向6)
s4：更新odd = r (此時(shí)odd指向5)
s5：更新r = r_next (此時(shí)r指向6)
更新后鏈表順序?yàn)椋?->3->5->2->4->6->7 (此時(shí)odd指向5，even指向4，r指向6)
復(fù)雜度O(n)，內(nèi)存O(1)
1 #328
2 #Runtime: 73 ms
3 #Memory: 17.1 MB
4
5 # Definition for singly-linked list.
6 # class ListNode(object):
7 # def __init__(self, val=0, next=None):
8 # self.val = val
9 # self.next = next
10 class Solution(object):
11 def oddEvenList(self, head):
12 """
13 :type head: ListNode
14 :rtype: ListNode
15 """
16 if not head:
17 return head
18 pos = 1
19 r = head.next
20 odd = head
21 even = head
22 while r:
23 if pos % 2:
24 even = r
25 r = r.next
26 else:
27 first_even = odd.next
28 r_next = r.next
29 odd.next = r
30 r.next = first_even
31 even.next = r_next
32 odd = r
33 r = r_next
34 pos += 1
35 return head