問題
Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.
You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.
Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.
Note:
The relative order inside both the even and odd groups should remain as it was in the input.
The first node is considered odd, the second node even and so on ...
大意：
給出一個(gè)簡單鏈表嗅定，集合所有奇數(shù)位置的節(jié)點(diǎn)蜜徽，后面跟著所有偶數(shù)位置的節(jié)點(diǎn)。請注意這里我們說的是節(jié)點(diǎn)的位置而不是節(jié)點(diǎn)值。
你應(yīng)該嘗試在固定空間做。程序應(yīng)該在O（1）的空間復(fù)雜度和O（nodes）的時(shí)間復(fù)雜度下運(yùn)行洋措。
例子：
給出 1->2->3->4->5->NULL，
返回 1->3->5->2->4->NULL救恨。
注意：
偶數(shù)和奇數(shù)組中節(jié)點(diǎn)的相對位置要保持不變缀匕。
第一個(gè)節(jié)點(diǎn)被認(rèn)為是奇數(shù)纳决，第二個(gè)是偶數(shù)，如此往復(fù)乡小。
思路：
題目的要求根據(jù)例子就可以明白阔加，奇數(shù)和偶數(shù)位置的節(jié)點(diǎn)分成兩段來排列，關(guān)鍵是要在O（1）的空間復(fù)雜度下做满钟，否則直接用一個(gè)新鏈表就可以簡單完成胜榔。
O（1）的空間下也好做，我們用兩個(gè)頭結(jié)點(diǎn)湃番，一個(gè)為奇數(shù)的頭結(jié)點(diǎn)夭织，一個(gè)為偶數(shù)的頭結(jié)點(diǎn)，然后遍歷鏈表吠撮，奇數(shù)位置的節(jié)點(diǎn)就記錄在奇數(shù)頭結(jié)點(diǎn)后面尊惰，偶數(shù)位置的節(jié)點(diǎn)就記錄在偶數(shù)頭結(jié)點(diǎn)后面，兩者是交替記錄的，因?yàn)槲覀冇玫倪€是原來的節(jié)點(diǎn)弄屡，只是next指針指向的節(jié)點(diǎn)變了题禀，所以并沒有增加空間。遍歷完后我們得到了奇偶兩條鏈表琢岩，將偶鏈表的頭結(jié)點(diǎn)接到奇鏈表的最尾端就可以了投剥。
要注意一些節(jié)點(diǎn)為Null的處理。
代碼（Java）：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode even = head.next;
ListNode evenNext = even;
ListNode oddNext = head;
while (evenNext != null) {
oddNext.next = evenNext.next;
if (oddNext.next != null) {
oddNext = oddNext.next;
evenNext.next = oddNext.next;
evenNext = evenNext.next;
} else {
break;
}
}
oddNext.next = even;
return head;
}
}
合集：https://github.com/Cloudox/LeetCode-Record
