題目
- 給定一個(gè)鏈表耗溜，將其奇數(shù)排序在前组力，偶數(shù)排序在后（相對(duì)位置的順序值，不是節(jié)點(diǎn)值）
- 舉例1->2->3->4->5排序后為1->3->5->2->4抖拴，2->1->3->5->6->4->7->NULL排序后為2->3->6->7->1->5->4->NULL
解題方法
- 有點(diǎn)類(lèi)似于leetcode86燎字，可以設(shè)置一個(gè)奇數(shù)鏈表和偶數(shù)鏈表，對(duì)原始鏈表進(jìn)行遍歷城舞，然后奇數(shù)節(jié)點(diǎn)放入奇數(shù)鏈表轩触，偶數(shù)節(jié)點(diǎn)放入偶數(shù)鏈表，最后奇數(shù)最后一個(gè)節(jié)點(diǎn)next指向偶數(shù)鏈表的頭節(jié)點(diǎn)家夺，返回奇數(shù)頭節(jié)點(diǎn)即可脱柱。
代碼實(shí)現(xiàn)1
/**
* 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 || head.next == null) return head;
ListNode odd = head, even = head.next;
ListNode oddLast = odd, evenLast = even;//奇偶數(shù)鏈表最后一個(gè)節(jié)點(diǎn)
head = head.next.next;
int count = 0;
while (head != null) {
count++;
ListNode temp = head;
head = head.next;
if (count % 2 == 0) {
temp.next = evenLast.next;
evenLast.next = temp;
evenLast = evenLast.next;
} else {
temp.next = oddLast.next;
oddLast.next = temp;
oddLast = oddLast.next;
}
}
oddLast.next = even;
evenLast.next = null;
return odd;
}
}
- 這個(gè)實(shí)現(xiàn)的時(shí)間消耗比較低，leetcode通過(guò)所需時(shí)間3ms
代碼實(shí)現(xiàn)2(和以上類(lèi)似)
private ListNode oddEvenListBackup(ListNode head) {
ListNode odd = new ListNode(0);
ListNode even = new ListNode(0);
ListNode oddIndex = odd, evenIndex = even;
ListNode temp = head;//暫存節(jié)點(diǎn)索引
int count = 0;
while (head != null) {
count++;
temp = head;
head = head.next;
if (count % 2 == 0) {
//偶數(shù)
temp.next = evenIndex.next;
evenIndex.next = temp;
evenIndex = evenIndex.next;
} else {
//奇數(shù)
temp.next = oddIndex.next;
oddIndex.next = temp;
oddIndex = oddIndex.next;
}
}
oddIndex.next = even.next;//奇數(shù)下一個(gè)置為偶數(shù)
return odd.next;
}
- 消耗時(shí)間6ms較高拉馋，因?yàn)樵黾恿祟^結(jié)點(diǎn)開(kāi)銷(xiāo)
