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.
題目不難理解我就不翻譯了滩援，就是一個單鏈表，把所有奇數(shù)的結(jié)點放在前面俭正，然后接著所有的偶數(shù)結(jié)點多搀，然后要求在時間復(fù)雜度O(n)和空間復(fù)雜度O(1)之下完成
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 ...
My Solution
(Java) Version 1 Time: 0ms:
一開始我以為和很久之前的題一樣正什，Java在單鏈表會有坑夫嗓，然后嘗試了多用幾個變量就會超過空間限制，后來破罐子破摔用回C語言的寫法沒有想到過了拔妥。
思路在于，把單鏈表分為奇數(shù)結(jié)點的鏈表和偶數(shù)結(jié)點鏈表兩個达箍，然后遍歷鏈表分別把奇數(shù)結(jié)點和偶數(shù)結(jié)點提取出來没龙，最后在兩條鏈表一接，完成……
/**
* 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 || head.next.next == null)
return head ;
ListNode odd = head , even = head.next , even_head = even;
while(even != null && even.next != null ){
odd.next = even.next ;
even.next = odd.next.next ;
odd = odd.next ;
even = even.next;
}
odd.next = even_head;
return head;
}
}
這破題沒有別的做法……
