逆轉(zhuǎn)交替合并兩個鏈表，即從一個鏈表的尾指針指向另一個鏈表的尾指針，依次逆轉(zhuǎn)交替進行合并。下面就通過實例來詳細(xì)的介紹該逆轉(zhuǎn)交替合并兩個鏈表的思路與實現(xiàn)代碼。

一、問題描述

鏈表A和B
A: 1->2->3->4
B: a->b->c->d
請逆轉(zhuǎn)交替合并兩個鏈表，示例結(jié)果如下：
4->d->3->c->2->b->1->a
節(jié)點類型定義如下:

classNode {
 public Node next;
 ...
}

二、源代碼：

傳入兩個A和B鏈表，返回處理后的鏈表：

Node reverse_merge(Node A, Node B) 
{ 
 //A、B都只有一個節(jié)點 
 if(A.next==null) 
 { 
 A.next=B; 
 return A; 
 } 
 //A、B都大于等于2個節(jié)點 
 Node nextA; 
 Node nextB; 
 
 nextB = B.next; 
 B.next = null; 
 nextA = A.next; 
 A.next = B; 
 B = nextB; 
 while (nextA.next != null) 
 { 
 B.next = A; 
 A = nextA; 
 nextA = A.next; 
 A.next = B; 
 B = nextB; 
 } 
 nextB.next = A; 
 nextA.next = B; 
 return nextA; 
} 

三、解析：

程序分成三個部分——while循環(huán)之前、while循環(huán)體、while循環(huán)之后。
1）處理之前的鏈表A和B

2）while循環(huán)——核心的處理部分
這里處理程序的可重復(fù)的部分，我們的目標(biāo)是紅色的部分，要達(dá)成紅色的鏈接模式，有兩個原子結(jié)構(gòu)：深紅色圓圈1和藍(lán)色圓圈2

但是1中需要特別處理a所在的節(jié)點，僅對于a所在的節(jié)點需要一個next=null的操作，也就是說1中的第一個原子要放在循環(huán)之外實現(xiàn)，這包括1指向a，b指向1的操作。

換種方式，如果使用2方式，就只需要將1指向a放在循環(huán)之外。所以，這里采用了2中描述的原子結(jié)構(gòu)。

原子結(jié)構(gòu)需要的信息

當(dāng)我們進行到某一次循環(huán)時，假設(shè)進行到藍(lán)色圓圈的操作了，這時候我們鏈表的狀態(tài)為：

更為直觀的畫法為：

它涉及到3個節(jié)點——2,3和c。其中紅色部分是我們希望做到的鏈接方式。為了鏈接c->2,3->c，必須知道有相應(yīng)的指針記錄他們的位置。所以在循環(huán)之前我們需要掌握這三個元素的地址，并且在處理完之后，用相同的方式表示下一次需要處理的原子結(jié)構(gòu)。

例如以下這種方式記錄這次循環(huán)中設(shè)計的3個節(jié)點的地址：

A、nA、B代表指向相應(yīng)節(jié)點的指針或者說是引用。

在處理完成之后需要用相同的方式記錄下一次原子結(jié)構(gòu)涉及的節(jié)點，這樣才能保證循環(huán)能夠按統(tǒng)一邏輯執(zhí)行下去，我們的目標(biāo)是：

這些賦值操作正是循環(huán)體的中代碼所做的事情，恰好代碼也是按照上面指定的命名形式，有一點區(qū)別，圖中的nA代表代碼中的nextA。除此之外，代碼中定義了nextB作為一個中間變量，用來記錄c->d斷開之前d節(jié)點的地址，因為c指向2之后就會失去對d的聯(lián)系，這個中間變量是必須的。

3）while循環(huán)之前——解決預(yù)備操作所帶來的問題

我們還沒有處理a節(jié)點，因為它太特殊了，沒有合適的原子結(jié)構(gòu)能包括它。所以我們把它放在循環(huán)體之外，并且為循環(huán)做好準(zhǔn)備工作，我們希望的結(jié)果是這樣：

在這之后我們就可以把1，2，b放在循環(huán)體中處理。這里也考慮了A、B都只有一個節(jié)點的情況，也需要單獨處理。

4）while循環(huán)之后——最后的處理

當(dāng)我們發(fā)現(xiàn)B鏈表到達(dá)末尾時，結(jié)束循環(huán)。但這時候并有處理末尾節(jié)點，換句話說，末尾節(jié)點不在原子結(jié)構(gòu)中。我們的循環(huán)會停止在這個原子結(jié)構(gòu)中：

作為最后的操作，我們需要手動處理d->3,4->d的鏈接步驟——這也是沒有辦法的，因為原子結(jié)構(gòu)的處理必須找到能夠把所有指針傳遞下去的節(jié)點，作為最后的節(jié)點是沒辦法吧指針繼續(xù)傳遞下去。

這不是一個完整的方法，還有很多事情沒有處理，比如輸入的A、B如果不等長，應(yīng)該如何處理。另外Node數(shù)據(jù)結(jié)構(gòu)并沒有完整的定義，不過這都不是本文討論的重點。

通過以上詳細(xì)的解析，希望能夠幫助大家很好的理解該逆轉(zhuǎn)交替合并兩個鏈表的方法與實現(xiàn)。

最新評論