今天學(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)排在后面。我們用張圖來表示下吧：

奇偶鏈表題目.png

實(shí)現(xiàn)思路

老規(guī)矩，先看解題思路圖。

奇偶鏈表-解題.png

難點(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)。而無(wú)需做特殊處理。

實(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;
}