今天學(xué)習(xí)的算法是奇偶鏈表，自己實(shí)現(xiàn)后發(fā)現(xiàn)雖然方法大致思路是對(duì)的爵川。但是最后提交完看解題答案發(fā)現(xiàn)竟然還可以這么簡(jiǎn)單敷鸦。
題目介紹
奇偶鏈表就是給定一個(gè)單向鏈表濒旦，將從頭部開始遍歷傻咖，次序?yàn)槠鏀?shù)的節(jié)點(diǎn)排在前面恢筝，序號(hào)為偶數(shù)的節(jié)點(diǎn)排在后面痊远。我們用張圖來表示下吧：
實(shí)現(xiàn)思路
老規(guī)矩哩簿，先看解題思路圖舆绎。
難點(diǎn)說明
1.定義三個(gè)變量兽叮，奇數(shù)尾節(jié)點(diǎn)累盗，偶數(shù)頭節(jié)點(diǎn)以及偶數(shù)尾節(jié)點(diǎn)洞焙。其中偶數(shù)頭節(jié)點(diǎn)固定賦值為頭節(jié)點(diǎn)的next節(jié)點(diǎn)蟆淀。
2.每次遍歷時(shí)先將奇數(shù)尾節(jié)點(diǎn)指向next的next節(jié)點(diǎn)，再將偶數(shù)尾節(jié)點(diǎn)指向next的next節(jié)點(diǎn)澡匪。原因是偶數(shù)節(jié)點(diǎn)一定在奇數(shù)節(jié)點(diǎn)后熔任，為了防止指針丟失。
3.從第2步可以看出唁情，循環(huán)結(jié)束的條件就是要求奇數(shù)尾節(jié)點(diǎn)的next和偶數(shù)尾節(jié)點(diǎn)的next都不為空疑苔。
重點(diǎn)關(guān)注下邊界情況，仔細(xì)分析
- 鏈表的長(zhǎng)度為奇數(shù)甸鸟，那么最后奇數(shù)尾節(jié)點(diǎn)和偶數(shù)尾節(jié)點(diǎn)的next都為null惦费，此時(shí)只要再進(jìn)行一步將奇數(shù)尾節(jié)點(diǎn)的next指向偶數(shù)頭節(jié)點(diǎn)即可。
- 鏈表的長(zhǎng)度為偶數(shù)抢韭，那么最后奇數(shù)尾節(jié)點(diǎn)和偶數(shù)尾節(jié)點(diǎn)的next都指向最后一個(gè)節(jié)點(diǎn)薪贫，而最后一個(gè)節(jié)點(diǎn)為偶數(shù)節(jié)點(diǎn)，因此仍然只需將奇數(shù)尾節(jié)點(diǎn)的next指向偶數(shù)頭節(jié)點(diǎn)即可刻恭。
綜上分析瞧省，算法實(shí)現(xiàn)時(shí)循環(huán)結(jié)束后最后一步都只需將奇數(shù)尾節(jié)點(diǎn)指向偶數(shù)頭節(jié)點(diǎn)。而無需做特殊處理鳍贾。
實(shí)現(xiàn)代碼
優(yōu)化前
public ListNode oddEvenList(ListNode head){
if(null == head || null == head.next){
return head;
}
ListNode oddTailNode = head;
ListNode evenHeadNode = head.next;
ListNode evenTailNode = head.next;
ListNode P = head.next.next;
int index = 1;
while (null != P){
if((index % 2)==1){
oddTailNode.next = P;
oddTailNode = P;
}else{
evenTailNode.next = P;
evenTailNode = P;
}
P = P.next;
index++;
}
evenTailNode.next = null;
oddTailNode.next = evenHeadNode;
return head;
}
優(yōu)化后
public ListNode oddEvenList(ListNode head) {
if (null == head || null == head.next) {
return head;
}
ListNode oddTail = head;
ListNode evenHead = head.next, evenTail = head.next;
while (null != oddTail.next && null != evenTail.next) {
oddTail.next = oddTail.next.next;
oddTail = oddTail.next;
evenTail.next = evenTail.next.next;
evenTail = evenTail.next;
}
oddTail.next = evenHead;
return head;
}
