第2章線性表

本章講解線性表。要求理解線性表概念、基本操作；掌握線性表的存儲結構；掌握順序表的基本操作；掌握鏈表的基本操作；靈活應用線性表。北京有冰糖葫蘆，咱們成都有糖油果子。老遠處看還真難以區分，在成都的北京人以為要吃到家鄉的冰糖葫蘆了；在北京的成都人以為要吃到家鄉的糖油果子了。哈哈，原來它們盡管味道霄壤之別，卻長得相像，皆是線性結構。提綱2.1線性表基本概念2.2順序表2.3單鏈表2.4雙鏈表2.5循環鏈表2.6線性表應用2.7線性表學習總結2.1線性表基本概念

2.1線性表基本概念如圖2.1所示，太陽公公和小朋友們手拉手，他的直接前驅是2號小朋友，直接后繼是4號小朋友；1號和5號小朋友分別是太陽公公的間接前驅和間接后繼。2.1線性表基本概念線性表的抽象數據接口描述如下：publicinterfaceIList{

publicvoidclear(); //將線性表置成空表

publicbooleanisEmpty(); //判斷線性表是否為空表

publicintlength(); //返回線性表的長度

publicObjectget(inti)throwsException;//獲取第i個元素

publicvoidinsert(inti,Objectx)throwsException;//i位置插入x

publicvoidremove(inti)throwsException;//刪除位置i的元素

publicintindexOf(Objectx); //返回元素x首次出現的位序號

publicvoiddisplay(); //輸出線性表所有元素

}

根據存儲結構不同，線性表分為順序表和鏈表2大類。2.2順序表以順序存儲結構進行存儲的線性表稱為順序表。2.2.1順序表存儲結構順序表存儲結構采用順序存儲方式，邏輯上相鄰的元素物理存儲位置也相鄰，元素存儲都是連續的。由這種結構特點可知，順序表可以隨機訪問快速定位某個元素，查找效率高，但刪除和插入元素時，需要移動大量元素，效率低。舉例：老師在教室里選擇1列或1行無空位連續坐著n個學生的區域，假設有座位編號，老師可以迅速定位某個學生，如3號學生玩手機優先回答問題吧；若把3號學生請出教室后仍保持這個區域順序存儲，則4號坐到3號處，5號坐到4號處，依此類推n號坐到n-1號處；若3號學生在教室外呆了一會兒反省了，老師又讓他坐回原來位置，則n-1號先坐回n號處。。。。。。此時的3號坐回4號處，原3號學生坐回3號處。在這個例子中，n個學生的區域是順序表存儲結構，對順序表的查找較容易而對其刪除和插入較麻煩。2.2.2順序表基本操作順序表類的描述如下：publicclassSeqListimplementsIList{

publicObject[]listItem;//順序表用一維數組作為存儲空間

publicintcurLen;//順序表當前長度

publicintmaxSize;//最大分配空間

publicSeqList(intmaxSize){//構造存儲空間為maxsize的順序表

curLen=0;

maxSize=maxSize;

listItem=newObject[maxSize];

}

//順序表基本操作（略）

}

2.2.2順序表基本操作

2.2.2順序表基本操作初始化創建初始化創建是為順序表分配一段預定義大小的連續空間，用listItem記錄首地址。初始化元素個數不超過最大分配空間即可，如算法2.1和圖2.2所示。2.2.2順序表基本操作

2.2.2順序表基本操作

2.2.2順序表基本操作查找順序表查找元素是指在順序表中查找與指定關鍵字key是否有相等的元素。如圖2.3所示查找與關鍵字相同的元素8，若找到則返回其位置，否則返回最后的-1。倘若查找的是3則返回1，查找的是5則返回3。那么如何實現的呢？我們來看看算法2.2。2.2.2順序表基本操作【算法2.2】在順序表中查找首次出現的元素8，若找到則返回其位置；若沒找到則返回-1。思路:（1）從第1個元素開始順序查找，依次比較每一個元素值。（2）若相等則找到，可返回元素位置。

（3）若遍歷完順序表都沒找到，則查找失敗，可返回-1。代碼見算法2_22.2.2順序表基本操作

2.2.2順序表基本操作【算法2.3】在順序表的i=2處插入元素7。思路：（1）如果順序表已滿，拋出異常；

（2）如果插入的位置超出[0,curLen]范圍，則拋出異常；

（3）如果i=curLen，則直接插入，否則執行（4）；

（4）從順序表最后1個元素開始依次往后移動，直到位置i上的元素移動；

（5）將元素elem插入到位置i處；

（6）將curLen加1，插入成功返回ture，否則返回false。代碼見算法2_32.2.2順序表基本操作刪除順序表刪除元素是指在順序表中若找到要刪除的元素elem則將其刪除，若沒找到則刪除失敗。如圖2.5所示刪除元素7前后的對比。若要刪除元素7，又如何實現的呢？我們來看看算法2.4。2.2.2順序表基本操作

2.3單鏈表由于鏈表的存儲在物理上元素之間可以連續也可以不連續，體現元素之間的關聯就需要附加1個指針域next，除了數據與data外。只有1個指針域指向其后繼的鏈表叫單鏈表，如圖2.6所示，其中指針域next也是單鏈表節點類型，這種結構稱為遞歸結構定義；符號“∧”表示空。2.3.1單鏈表存儲結構單鏈表存儲結構采用鏈式存儲方式，邏輯上相鄰的元素物理存儲位置不一定相鄰，元素存儲是離散的。由這種結構特點可知，單鏈表不能隨機存取，查找效率低，但刪除和插入元素時，不需要移動大量元素，效率高。舉例：教室里的學生并沒有按照學號順序依次坐，中間空位也多，不必連續，這叫入座自由！老師考勤，讓學生從小到大自報學號后2位，你看看“遍地開花”！為什么亂坐現象能夠順序點名？因為每個學生的學號（加1）可以看作指向下一個學生的指針，上一個學生找到了那么下一個學生也就找到了，與他們之間所坐的物理位置無關！在這個例子中，教室里的學生可以看作構成單鏈表的節點元素，所有學生構成單鏈表。2.3.2單鏈表基本操作單鏈表節點類Node描述單鏈表類LinkList描述2.3.2單鏈表基本操作1.初始化單鏈表初始化操作是指創建一個空表。空表往往只有頭節點head，不存儲數據，頭節點的指針域為空，如下圖所示。頭節點的作用：（1）找到相應的單鏈表，好比穿衣服抓到衣領；（2）方便一些從頭節點開始的操作如遍歷查找。2.3.2單鏈表基本操作【算法2.5】單鏈表初始化。publicvoidalgorithm2_5(Objectelem)throwsException{

LinkList=newLinkList(); //創建單鏈表

System.out.println(linkList.head.data);//驗證單鏈表頭節點數據域空

System.out.println(linkList.head.next);//驗證單鏈表頭節點指針域空

}

算法2.5，用單鏈表類的不帶參數的構造方法創建了只有頭節點的單鏈表空表，且頭節點不包含任何內容。2.3.2單鏈表基本操作2.插入單鏈表插入操作是指將節點s插入節點p的后面。如圖2.8所示的插入過程又如何實現的呢？我們來看看算法2.6。2.3.2單鏈表基本操作【算法2.6】在帶頭節點的單鏈表中將節點s插入到節點p之后。思路：（1）從單鏈表頭節點開始遍歷，尋找節點p；（2）若遍歷完之后沒找到，則返回false，否則執行（3）；（3）若節點p是尾節點，則將p的next指向s，s的next置為null，返回true；（4）若節點p不是尾節點，則將節點s的next指向節點p原來的后繼；將節點p的next指向節點s，返回true。代碼見算法2_6（）2.3.2單鏈表基本操作【思考與練習2.1】在圖2.8中，2個新增的指針（見①②），賦值的先后順序可否改變，即s.next=p.next;與p.next=s;這2條語句可否交換順序，為什么？答：不能！如果交換順序，p.next=s;沒問題，節點p指向了插入后的節點s，但s.next=p.next;就是s指向自己，因為此時的p指向的是s，而非原來的后繼。所以只能按照順序進行操作。2.3.2單鏈表基本操作3.整表創建單鏈表整表創建操作是指一次性創建并初始化單鏈表一些元素，它可由尾插法和頭插法進行整表創建。顧名思義，尾插法是將插入元素始終在單鏈表的尾部插入；頭插法是將插入元素始終在單鏈表的頭部插入。舉例：請1到5學號的同學依次上講臺來，從左到右的面向方向：1號上來，2號在1號后面，3號在2號后面，依次類推，最后排列的順序與上來的順序一樣；再來一遍，上來的順序不變，1號上來，2號在1號的前面，3號在2號的前面，依次類推，最后排列的順序與上來的順序相反。通過這個例子，顯然我們得知：尾插法的結果是順序/正序，頭插法的結果是逆序/倒序。2.3.2單鏈表基本操作如圖2.9所示，每產生1個新節點s，始終將其插入單鏈表的尾部或頭部（頭節點head之后）。那么又如何實現尾插法和頭插法整體建表的呢？我們來看看算法2.7和算法2.8。2.3.2單鏈表基本操作【算法2.7】用尾插法創建單鏈表。思路：（1）移動指針t指向頭節點head；（2）在t的后面插入單鏈表新節點s；（3）t移動到s；（4）重復執行（2）、（3），直到數組a遍歷完；（5）置t的指針域為null。代碼見算法2_7()2.3.2單鏈表基本操作【算法2.8】用頭插法創建單鏈表。思路：（1）遍歷數組a，每次產生1個單鏈表新節點s；（2）在單鏈表的頭節點head之后插入s；（3）重復執行（1）、（2），直到數組a遍歷完。代碼見算法2_8()（備注：游戲視頻演示細節有問題，請同學指出）2.3.2單鏈表基本操作【思考與練習2.2】可否利用算法2.6實現單鏈表的尾插法和頭插法？答：可以的。在尾插法中，始終將節點p置為尾節點，遍歷數組a時調用算法2.6進行插入；在頭插法中，始終將節點p置為頭節點head，遍歷數組a時調用算法2.6進行插入。如thinkpad2_2算法。2.3.2單鏈表基本操作4.取值單鏈表取值操作是指取到第i個元素的值，將其值返回；若沒取到則返回-1。舉例：我要找到教室里學號為18的學生，我可以讓學生從1號開始報號，直到報到18號。倘若要找學號為88的學生，報完了也找不到！因為超出取值范圍了。2.3.2單鏈表基本操作如圖2.10所示，要取到單鏈表中第i個元素的值ai，又如何實現的呢？我們來看看算法2.9。2.3.2單鏈表基本操作【算法2.9】單鏈表中取第i個元素的值。思路：（1）節點p設為從首節點開始遍歷單鏈表的指針，計數變量j初值為1；（2）每遍歷到1個節點時，判斷j是否等于i：若相當則返回p指向節點的值；若不等則p繼續移動，j加1；（3）重復（2），直到找到而返回，或遍歷完而沒找到返回-1。代碼見算法2_9()2.3.2單鏈表基本操作5.查找單鏈表查找操作是指在單鏈表中查找與指定關鍵字key是否相同的元素。單鏈表不能像順序表那樣隨機存取，所以查找過程是從頭節點或首節點開始依次遍歷比較的過程。如圖2.11所示，查找單鏈表中是否有key=“FanFan”的節點，若找到第1個這樣的節點則查找成功返回true；若沒找到則返回false。又如何實現的呢？我們來看看算法2.10。2.3.2單鏈表基本操作【算法2.10】單鏈表中查找key=“FanFan”的第1個節點。思路：（1）節點p設為從首節點開始遍歷單鏈表的指針；（2）取出p的數據域值，與指定關鍵字key比較：若相等則找到，返回true；若不相等則繼續找下一個元素，執行（3）；（3）重復（2），直到找到而返回true，或遍歷完而沒找到返回false。代碼見算法2_10()2.3.2單鏈表基本操作6.刪除單鏈表刪除操作是指將單鏈表中位置為i的節點從單鏈表中刪除。單鏈表刪除操作有點像“跳過”要刪除的節點，好比a、b、c三人手拉手，ac牽手則b出去了，如圖2.12所示，要刪除i位置處的b節點，只需（i-1）位置處的a節點的指針域指向節點b的后繼c即可。那么代碼又如何實現的呢？我們來看看算法2.11。2.3.2單鏈表基本操作【算法2.11】單鏈表中刪除位置為i的b節點。思路：（1）設置1個移動指針p，初始指向頭節點head；（2）將p移動到（i-1）位置處；（3）將p指向的節點的指針域修改為該節點的后繼的后繼。代碼見算法2_11()2.4雙鏈表雙鏈表雙鏈表有2個指針域，顧名思義。比單鏈表在節點結構上多了1個指針域prior：指向前驅的指針域，它解決了單鏈表只能向后操作的問題。雙鏈表的頭節點也有2個指針域，如圖2.13所示帶頭節點的雙鏈表邏輯結構。2.4.1雙鏈表存儲結構雙鏈表存儲結構類同單鏈表，也是采用鏈式存儲方式，也有與單鏈表共同的特性如增刪節點高效。由于有2個指針域，所以雙鏈表既可以利用next指針域向后操作，也可以利用prior指針域向前操作。這一特性又可以改變一些單鏈表算法思路。2.4.1雙鏈表存儲結構舉例：請5個同學上講臺，從左到右1到5編號。（1）單鏈表游戲表演：5個同學向左轉，雙手搭在下一個同學肩膀上（最后1個同學除外）；從1號開始，雙手使勁搖下2號肩膀，表示2號存活，2號再使勁去搖3號肩膀，3號存活，依此類推。其實我們要出局3號，2號一不小心搖了他，他又搖了4號，4號沒有對3號的生死權，游戲只得從頭再來。（2）雙鏈表游戲表演：5個同學面向教室手拉手，1號搖搖左手，2號存活，2號搖搖左手3號存活，3號搖搖左手，4號存活；4號或者此時的觀眾想起來了，3號要出局！莫慌，4號懶得搖搖右手了，直接去牽2號的左手，3號出局！倘若到5號才想起3號要出局，5號搖搖右手，4號冰雪聰明：牽2號左手！2.4.2雙鏈表基本操作雙鏈表節點類DuLNode描述雙鏈表類DuLinkList描述2.4.2雙鏈表基本操作1.初始化雙鏈表的初始化操作是指構建1個空表，建頭節點而不存儲數據，頭節點的2個指針域皆為空，如圖2.14所示。

2.4.2雙鏈表基本操作【算法2.12】雙鏈表初始化。publicvoidalgorithm2_12(Objectelem)throwsException{

DuLinkListduLinkList=newDuLinkList();//創建雙鏈表

System.out.println(duLinkList.head.prior);//驗證頭節點前驅域為空

System.out.println(duLinkList.head.data);//驗證頭節點數據域為空

System.out.println(duLinkList.head.next);//驗證頭節點后繼域為空

}

算法2.12，用雙鏈表類的不帶參數的構造方法創建了只有頭節點的雙鏈表空表，且頭節點不包含任何內容。2.4.2雙鏈表基本操作2.插入雙鏈表插入操作同單鏈表插入操作，不同的是在插入過程中單鏈表改變的是2個指針，雙鏈表改變的是4個指針，除非是尾部插入和不帶頭節點的頭部插入。不妨仍將節點s插入節點p的后面，如圖2.15所示的插入過程又如何實現的呢？我們來看看算法2.13。2.4.2雙鏈表基本操作【算法2.13】在帶頭節點的雙鏈表中將節點s插入到節點p之后。思路：（1）從雙鏈表頭節點開始遍歷，尋找節點p；（2）若遍歷完之后沒找到，則返回false，否則執行（3）；（3）若節點p是尾節點，則將p的next指向s；將s的prior指向p；將s的next置為null，返回true；（4）若節點p不是尾節點，則將節點s的next指向節點p原來的后繼；將節點p原來的后繼的prior指向s；將節點s的prior指向p；將節點p的next指向s；返回true。代碼見算法2.132.4.2雙鏈表基本操作【思考與練習2.3】在雙鏈表的插入操作中，若節點p是節點s的后繼，能否實現插入，若不能為什么；若可以又如何實現？答：可以！如圖2.16所示，從左到右4個指針分別執行①②④③，也可以是①③④②。如下面的算法：publicvoidthinkPad2_3()throwsException{

//雙鏈表，由后繼或者在當前節點處插入操作的主要代碼：

/*

s.prior=p.prior;

p.prior.next=s;

s.next=p;

p.prior=s;

*/

}

在雙鏈表的插入操作中，可以隨便改變4個指針更新的順序嗎？答：不能！同單鏈表，見【思考與練習2.1】解答。2.4.2雙鏈表基本操作3.整表創建雙鏈表整表創建操作同單鏈表整表創建操作，也可由尾插法和頭插法進行整表創建。不同的是，它更新的指針更多。那么又如何實現的呢？我們來看看算法2.14和2.15。【算法2.14】用尾插法創建雙鏈表。思路：（1）移動指針t指向頭節點head；（2）在t的后面插入雙鏈表新節點s；（3）t移動到s；（4）重復執行（2）、（3），直到數組a遍歷完；（5）置t的指針域為null。代碼見算法2.142.4.2雙鏈表基本操作【算法2.15】用頭插法創建雙鏈表。思路：（1）遍歷數組a，每次產生1個雙鏈表新節點s；（2）在雙鏈表的頭節點head之后插入s；（3）重復執行（1）、（2），直到數組a遍歷完。代碼見算法2.15同單鏈表整表創建一樣，雙鏈表整表創建也可以多次調用其“插入”函數高級編程實現。2.4.2雙鏈表基本操作4.取值雙鏈表取值操作同單鏈表取值操作，不同的是雙鏈表取值可以從前開始，也可以從后開始取值，由于雙鏈表雙向操作特點。【算法2.16】雙鏈表中取第i個元素的值。思路：（1）節點p設為從首節點開始遍歷雙鏈表的指針，計數變量j初值為1；（2）每遍歷到1個節點時，判斷j是否等于i：若相當則返回p指向節點的值；若不等則p繼續移動，j加1；（3）重復（2），直到找到而返回，或遍歷完而沒找到返回-1。代碼見算法2.162.4.2雙鏈表基本操作【思考與練習2.4】在雙鏈表的取值操作中，如果當前節點p為尾節點，取值節點的位置i靠近尾節點，顯然這種情況從“尾”開始比從“頭”開始好！那么如何實現從尾節點開始逆向遍歷取到節點值呢？答：如下面的算法：publicObjectthinkPad2_4(inti)throwsException{

DuLinkListduLinkList=newDuLinkList();//創建空雙鏈表

//假設雙鏈表中初始化了一些元素（略）

intlength=0;//雙鏈表長度

DuLNodep=duLinkList.head;//p為移動指針，初始指向頭節點

while(p.next!=null){

length++;

p=p.next;

}//置p為尾節點，并計算出雙鏈表長度

intj=length;

while(p!=null){//未遍歷完單鏈表

if(j==i)//找到

returnp.data;

else{//還沒找到

p=p.prior;//繼續往前找

j--;//計數變量減1，逆向遍歷

}

}

return-1;//沒找到返回-1

}

2.4.2雙鏈表基本操作留意：遍歷鏈表時注意循環條件，如p.next！=null和p！=null兩個條件，在最后遍歷完鏈表后，當前指針p位置是不同的，前者最后指向尾節點，后者最后為null（指向尾節點之后）。2.4.2雙鏈表基本操作5.查找雙鏈表查找操作同單鏈表查找操作，不同的是雙鏈表可以雙向查找。如圖2.17所示，查找雙鏈表中是否有key=“Vivian”的元素，假設這個元素若存在則是唯一的，且在中間位置偏左一點；若找到則返回true，否則返回false。那么又如何實現的呢？我們來看看算法2.17。2.4.2雙鏈表基本操作【算法2.17】雙鏈表中查找中間位置偏左一點且key=“Vivian”的節點。思路：（1）準備1個帶節點編號的雙鏈表，并初始化一些數據；（2）假設當前指針p已經走到雙鏈表的中間位置；（3）取出p的數據域值，與指定關鍵字key比較：若相等則找到，返回true；若不相等則向前移動1個位置，執行（4）；（4）重復（3），直到找到而返回true。代碼見算法2.172.4.2雙鏈表基本操作6.刪除雙鏈表刪除操作同單鏈表同單鏈表刪除操作，不同的是雙鏈表刪除操作可以從被刪除節點的前驅進行，也可以從其后繼進行。如圖2.18所示通過被刪除節點的前驅或后繼p進行刪除，那么代碼又如何實現的呢？我們來看看算法2.18。2.4.2雙鏈表基本操作【算法2.18】雙鏈表中刪除位置為i的b節點。思路：（1）設置1個移動指針p，初始指向頭節點head；（2）將p移動到（i-1）或（i+1）位置處；（3）p為被刪節點的前驅時：a.p后繼的后繼的prior指向p；b.p的next指向后繼的后繼。p為被刪節點的后繼時：a.p的前驅的前驅的next指向p；b.p的prior指向前驅的前驅。代碼見算法2.182.4.2雙鏈表基本操作【思考與練習2.5】在圖2.18中，①和②的操作順序是否可以交換，為什么？答：可以，因為指針域變化不受影響。不過建議先操作離當前節點p較遠的操作，即遵循“遠端優先操作”原則。如下面的算法：publicvoidthinkPad2_5()throwsException{

//p為被刪節點前驅，①和②交換：

/*

p.next=p.next.next;//p的next指向后繼的后繼

p.next.next.prior=p;//p后繼的后繼的prior指向p

*/

//p為被刪節點后繼，①和②交換：

/*

p.prior=p.prior.prior;//p的prior指向前驅的前驅

p.prior.prior.next=p;//p的前驅的前驅的next指向p

*/

}2.5循環鏈表循環鏈表是在之前所講的單鏈表、雙鏈表的基礎上改進而得的鏈表。由單鏈表改進得到循環單鏈表，由雙鏈表改進得到循環雙鏈表。它們的改進有個共同特點：首尾相連，形成環。為了更好區分這4種鏈表，見下面的例子。舉例：請5個同學自告奮勇上臺。第1個動作：站成一排，除最后1個同學外，其他同學的左手搭在左旁同學肩上。第2個動作：站成一排，手拉手吧！第3個動作：圍成圈，左手搭在左旁同學肩上。第4個動作：圍成圈，手拉手。通過這個例子我們可以很形象而生動地認識到，4個動作分別說的就是單鏈表、雙鏈表、循環單鏈表、循環雙鏈表，大概括啊！2.5循環鏈表循環單鏈表和循環雙鏈表的存儲結構與單鏈表和雙鏈表的存儲結構相同。2.5.1循環單鏈表循環單鏈表的尾節點的next不再為空，是指向頭節點，這樣使整個單鏈表形成環；若只有頭節點的空表，頭節點的next也指向頭節點自身。如圖2.19所示。2.5.1循環單鏈表循環單鏈表的節點類與單鏈表的節點類相同，鏈表類和基本操作相似，主要不同在于：循環單鏈表需通過head.next=head;語句置空表；判斷尾節點時不再是單鏈表的p.next==null;而是p.next==head;語句。2.5.1循環單鏈表循環單鏈表類CLinkList的描述2.5.2循環雙鏈表循環雙鏈表的尾節點的next也指向頭節點，頭節點的prior不再為空，是指向尾節點，這樣使整個雙鏈表形成環；若只有頭節點的空表，頭節點的next和prior皆指向頭節點自身。如圖2.20所示。2.5.2循環雙鏈表循環雙鏈表與雙鏈表的節點類相同，鏈表類和基本操作相似，主要不同在于：循環雙鏈表需通過head.next=head;和head.prior=head;語句置空表；判斷尾節點時不再是雙鏈表的p.next==null;而是p.next==head;語句。，2.5.2循環雙鏈表循環雙鏈表類CDuLinkList的描述2.6線性表應用2.6.1順序表應用【例2.1】將含有n個元素的有序順序表S中的所有元素逆置。如S=（1,2,3,4,5），逆置后S=（5,4,3,2,1），并分析算法的時空復雜度。思路：（1）雙指針設置：頭指針i和尾指針j；（2）交換它們所指向的元素后；（3）i++且j--，若i<j則執行（2），否則結束。代碼見例2.1算法2.6.1順序表應用【進一步思考】請寫出實現例2.1算法的其他思路。答：（1）逆序遍歷思路（2）入棧和出棧思路。等等。2.6.1順序表應用【例2.2】將含有n個整數元素的順序表S中相鄰重復元素刪掉，只保留1個。如S=（1,3,3,4,1），刪除后S=（1,3,4,1），并分析算法的時空復雜度。思路：（1）新建一個順序表，將原順序表第1個元素插入；（2）從原順序表第2個元素開始遍歷，比較新順序表中尾元素：若相等則繼續遍歷，若不相等則將其插入到新表中；（3）直到原順序表遍歷完成。代碼見例2.2算法2.6.1順序表應用【進一步思考】請寫出實現例2.2算法的其他思路。答：第1次遍歷找到相鄰相同的元素，第2次遍歷相鄰不相同的元素與之合并。等等。2.6.2單鏈表應用【例2.3】將含有n個元素的有序單鏈表L中的所有元素逆置。如L=（1,2,3,4,5），逆置后L=（5,4,3,2,1），并分析算法的時空復雜度。思路：（1）p指向單鏈表首節點；（2）置L為空單鏈表；（3）遍歷L，將p插入到L的頭部。代碼見例2.3算法2.6.2單鏈表應用【進一步思考】請寫出實現例2.3算法的其他思路。答：（1）頭尾雙指針交換，同例2.1算法思路(雙鏈表而言)（2）順序遍歷入棧，再出棧尾插法成單鏈表思路。等等。2.6.2單鏈表應用【例2.4】將2個遞增有序整數單鏈表A和B合并為C，C也是遞增有序單鏈表，并分析算法的時空復雜度。思路：（1）采用二路歸并和尾插法思想，在同時遍歷A和B時，比較元素大小；（2）將