給定一個單鏈表刀闷，把所有的奇數(shù)節(jié)點和偶數(shù)節(jié)點分別排在一起。請注意仰迁，這里的奇數(shù)節(jié)點和偶數(shù)節(jié)點指的是節(jié)點編號的奇偶性甸昏，而不是節(jié)點的值的奇偶性。
請嘗試使用原地算法完成徐许。你的算法的空間復(fù)雜度應(yīng)為 O(1)施蜜，時間復(fù)雜度應(yīng)為 O(nodes)，nodes 為節(jié)點總數(shù)雌隅。
示例 1:
輸入: 1->2->3->4->5->NULL
輸出: 1->3->5->2->4->NULL
示例 2:
輸入: 2->1->3->5->6->4->7->NULL
輸出: 2->3->6->7->1->5->4->NULL
說明:
- 應(yīng)當(dāng)保持奇數(shù)節(jié)點和偶數(shù)節(jié)點的相對順序翻默。
- 鏈表的第一個節(jié)點視為奇數(shù)節(jié)點，第二個節(jié)點視為偶數(shù)節(jié)點澄步，以此類推冰蘑。
思路：
一個 LinkedList 需要一個頭指針和一個尾指針來支持雙端操作。我們用變量 head 和 odd 保存奇鏈表的頭和尾指針村缸。 evenHead 和 even 保存偶鏈表的頭和尾指針祠肥。算法會遍歷原鏈表一次并把奇節(jié)點放到奇鏈表里去、偶節(jié)點放到偶鏈表里去。遍歷整個鏈表我們至少需要一個指針作為迭代器仇箱。這里 odd 指針和 even 指針不僅僅是尾指針县恕，也可以扮演原鏈表迭代器的角色。
image.png
解法：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode oddEvenList(ListNode head) {
if(head==null){return head;}
ListNode odd = head, even = head.next, evenHead = even;
while(even!=null && even.next != null){
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
}
