Odd Even Linked List (M)
題目
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 1:
Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL
Example 2:
Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL
Constraints:
- 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 ...
- The length of the linked list is between
[0, 10^4].
題意
將給定鏈表的奇數結點移到前半部分，偶數結點移到后半部分，(奇偶性指結點本身而不是結點內的數)
思路
將奇偶結點拆成兩個鏈表再合并即可，
代碼實作
Java
class Solution {
public ListNode oddEvenList(ListNode head) {
ListNode oddDummy = new ListNode();
ListNode odd = oddDummy;
ListNode evenDummy = new ListNode();
ListNode even = evenDummy;
boolean isOdd = true;
while (head != null) {
if (isOdd) {
odd.next = head;
odd = head;
} else {
even.next = head;
even = head;
}
head = head.next;
isOdd = !isOdd;
}
even.next = null;
odd.next = evenDummy.next;
return oddDummy.next;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/33851.html
標籤：其他
下一篇：位運算（一）