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

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

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

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

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

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