問(wèn)題
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è)簡(jiǎn)單鏈表，集合所有奇數(shù)位置的節(jié)點(diǎn)，后面跟著所有偶數(shù)位置的節(jié)點(diǎn)。請(qǐng)注意這里我們說(shuō)的是節(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)的相對(duì)位置要保持不變。
第一個(gè)節(jié)點(diǎn)被認(rèn)為是奇數(shù)，第二個(gè)是偶數(shù)，如此往復(fù)。
思路：
題目的要求根據(jù)例子就可以明白，奇數(shù)和偶數(shù)位置的節(jié)點(diǎn)分成兩段來(lái)排列，關(guān)鍵是要在O（1）的空間復(fù)雜度下做，否則直接用一個(gè)新鏈表就可以簡(jiǎn)單完成。
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)槲覀冇玫倪€是原來(lái)的節(jié)點(diǎn)，只是next指針指向的節(jié)點(diǎn)變了，所以并沒(méi)有增加空間。遍歷完后我們得到了奇偶兩條鏈表，將偶鏈表的頭結(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
