給定一個(gè)單鏈表，把所有的奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)分別排在一起。請(qǐng)注意芍瑞，這里的奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)指的是節(jié)點(diǎn)編號(hào)的奇偶性，而不是節(jié)點(diǎn)的值的奇偶性褐墅。
請(qǐng)嘗試使用原地算法完成拆檬。你的算法的空間復(fù)雜度應(yīng)為 O(1)，時(shí)間復(fù)雜度應(yīng)為 O(nodes)妥凳，nodes 為節(jié)點(diǎn)總數(shù)竟贯。
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/odd-even-linked-list
輸入: 1->2->3->4->5->NULL
輸出: 1->3->5->2->4->NULL
代碼：
if(head==null){
return null;
}
ListNode node2=head.next;
ListNode odd=head;
ListNode even=node2;
while(even!=null && even.next!=null){
odd.next=even.next;
odd=odd.next;
even.next=odd.next;
even=even.next;
}
odd.next=node2;
return head;
}
思路：
對(duì)于原始鏈表，每個(gè)節(jié)點(diǎn)都是奇數(shù)節(jié)點(diǎn)或偶數(shù)節(jié)點(diǎn)逝钥。頭節(jié)點(diǎn)是奇數(shù)節(jié)點(diǎn)屑那，頭節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)是偶數(shù)節(jié)點(diǎn)，相鄰節(jié)點(diǎn)的奇偶性不同艘款。因此可以將奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)分離成奇數(shù)鏈表和偶數(shù)鏈表持际，然后將偶數(shù)鏈表連接
在奇數(shù)鏈表之后，合并后的鏈表即為結(jié)果鏈表哗咆。
原始鏈表的頭節(jié)點(diǎn) head 也是奇數(shù)鏈表的頭節(jié)點(diǎn)以及結(jié)果鏈表的頭節(jié)點(diǎn)蜘欲，head 的后一個(gè)節(jié)點(diǎn)是偶數(shù)鏈表的頭節(jié)點(diǎn)。令 evenHead = head.next晌柬，則 evenHead 是偶數(shù)鏈表的頭節(jié)點(diǎn)姥份。
維護(hù)兩個(gè)指針 odd 和 even 分別指向奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)，初始時(shí) odd = head年碘，even = evenHead澈歉。通過(guò)迭代的方式將奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)分離成兩個(gè)鏈表，每一步首先更新奇數(shù)節(jié)點(diǎn)盛泡，然后更新偶數(shù)節(jié)點(diǎn)闷祥。
作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/odd-even-linked-list/solution/qi-ou-lian-biao-by-leetcode-solution/
來(lái)源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處凯砍。
