題目描述
給定一個(gè)單鏈表，把所有的奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)分別排在一起氨距。請注意，這里的奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)指的是節(jié)點(diǎn)編號的奇偶性棘劣，而不是節(jié)點(diǎn)的值的奇偶性俏让。
請嘗試使用原地算法完成。你的算法的空間復(fù)雜度應(yīng)為 O(1)茬暇，時(shí)間復(fù)雜度應(yīng)為 O(nodes)首昔，nodes 為節(jié)點(diǎn)總數(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é)點(diǎn)和偶數(shù)節(jié)點(diǎn)的相對順序糙俗。
- 鏈表的第一個(gè)節(jié)點(diǎn)視為奇數(shù)節(jié)點(diǎn)勒奇，第二個(gè)節(jié)點(diǎn)視為偶數(shù)節(jié)點(diǎn)，以此類推臼节。
分析
隔一個(gè)取一個(gè)元素撬陵，新建一個(gè)鏈表，把取出來的索引為偶數(shù)的元素放進(jìn)去网缝，原鏈表剩下的都是索引為奇數(shù)的元素巨税，再把兩個(gè)鏈表拼接起來，就可以得到結(jié)果粉臊。示意圖如下：
奇偶鏈表分步示意圖
源碼
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null) return null;
ListNode odd = head;
ListNode even = odd.next;
ListNode evenHead = even;
while (even != null && even.next != null) // 之所以不用奇指針判斷草添，是因?yàn)榕紨?shù)指針比奇數(shù)指針先到鏈表尾部
{
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
}
有一個(gè)小細(xì)節(jié)需要注意一下，在判斷鏈表是否走完的時(shí)候扼仲，我們要使用偶指針判斷远寸，因?yàn)樵诔跏嘉恢茫贾羔樖窃谄嬷羔樀暮竺嬉粋€(gè)位置屠凶，在若干輪的操作過后驰后，偶指針比奇指針先到達(dá)鏈表尾部。
