算法大全-面試題-數(shù)據(jù)結(jié)構(gòu)

1、一、單鏈表一、單鏈表目錄1.單鏈表反轉(zhuǎn)2.找出單鏈表的倒數(shù)第4個(gè)元素3.找出單鏈表的中間元素4.刪除無頭單鏈表的一個(gè)節(jié)點(diǎn)5.兩個(gè)不交叉的有序鏈表的合并6.有個(gè)二級(jí)單鏈表，其中每個(gè)元素都含有一個(gè)指向一個(gè)單鏈表的指針。寫程序把這個(gè)二級(jí)鏈表稱一級(jí)單鏈表。7.單鏈表交換任意兩個(gè)元素（不包括表頭）8.判斷單鏈表是否有環(huán)？如何找到環(huán)的“起始”點(diǎn)？如何知道環(huán)的長度？9.判斷兩個(gè)單鏈表是否相交10.兩個(gè)單鏈表相交，計(jì)算相交點(diǎn)11.用鏈表模擬大整數(shù)加法運(yùn)

2、算12.單鏈表排序13.刪除單鏈表中重復(fù)的元素首先寫一個(gè)單鏈表的C#實(shí)現(xiàn)，這是我們的基石：publicclassLinkpublicLinkNextpublicstringDatapublicLink(Linknextstringdata)this.Next=nextthis.Data=data其中，我們需要人為地在單鏈表前面加一個(gè)空節(jié)點(diǎn)，稱其為head。例如，一個(gè)單鏈表是125，如圖所示：對(duì)一個(gè)單鏈表的遍歷如下所示：staticvoi

3、dMain(string[]args)Linkhead=GenerateLink()Linkcurr=headwhile(curr!=null)算法2：自然是遞歸如果題目簡化為逆序輸出這個(gè)單鏈表，那么遞歸是很簡單的，在遞歸函數(shù)之后輸出當(dāng)前元素，這樣能確保輸出第N個(gè)元素語句永遠(yuǎn)在第N1個(gè)遞歸函數(shù)之后執(zhí)行，也就是說第N個(gè)元素永遠(yuǎn)在第N1個(gè)元素之后輸出，最終我們先輸出最后一個(gè)元素，然后是倒數(shù)第2個(gè)、倒數(shù)第3個(gè)，直到輸出第1個(gè)：publicst

4、aticvoidReverseLink2(Linkhead)if(head.Next!=null)ReverseLink2(head.Next)Console.WriteLine(head.Next.Data)但是，現(xiàn)實(shí)應(yīng)用中往往不是要求我們逆序輸出（不損壞原有的單鏈表），而是把這個(gè)單鏈表逆序（破壞型）。這就要求我們?cè)谶f歸的時(shí)候，還要處理遞歸后的邏輯。首先，要把判斷單鏈表有0或1個(gè)元素這部分邏輯獨(dú)立出來，而不需要在遞歸中每次都比較一次：

5、publicstaticLinkReverseLink3(Linkhead)ifnoelementsonlyoneelementexistsif(head.Next==null||head.Next.Next==null)returnheadhead.Next=ReverseLink(head.Next)returnhead我們觀測到：head.Next=ReverseLink(head.Next)這句話的意思是為ReverseLink