目錄
1.單鏈表反轉
2.找出單鏈表的倒數第4個元素
3.找出單鏈表的中間元素
4.刪除無頭單鏈表的一個節點
5.兩個不交叉的有序鏈表的合並
6.有個二級單鏈表，其中每個元素都含有一個指向一個單鏈表的指針。寫程序把這個二級鏈表稱一級單鏈表。
7.單鏈表交換任意兩個元素（不包括表頭）
8.判斷單鏈表是否有環？如何找到環的“起始”點？如何知道環的長度？
9.判斷兩個單鏈表是否相交
10.兩個單鏈表相交，計算相交點
11.用鏈表模擬大整數加法運算
12.單鏈表排序
13.刪除單鏈表中重復的元素
首先寫一個單鏈表的C#實現，這是我們的基石：
public class Link
{
public Link Next;
public string Data;
public Link(Link next, string data)
{
this.Next = next;
this.Data = data;
}
}
其中，我們需要人為地在單鏈表前面加一個空節點，稱其為head。例如，一個單鏈表是1->2->5，如圖所示：
對一個單鏈表的遍歷如下所示：
static void Main(string[] args)
{
Link head = GenerateLink();
Link curr = head;
while (curr != null)
{
Console.WriteLine(curr.Data);
curr = curr.Next;
}
}
這道題目有兩種算法，既然是要反轉，那麼肯定是要破壞原有的數據結構的：
算法1：我們需要額外的兩個變量來存儲當前節點curr的下一個節點next、再下一個節點nextnext：
public static Link ReverseLink1(Link head)
{
Link curr = head.Next;
Link next = null;
Link nextnext = null;
//if no elements or only one element exists
if (curr == null || curr.Next == null)
{
return head;
}
//if more than one element
while (curr.Next != null)
{
next = curr.Next; //1
nextnext = next.Next; //2
next.Next = head.Next; //3
head.Next = next; //4
curr.Next = nextnext; //5
}
return head;
}
算法的核心是while循環中的5句話
我們發現，curr始終指向第1個元素。
此外，出於編程的嚴謹性，還要考慮2種極特殊的情況：沒有元素的單鏈表，以及只有一個元素的單鏈表，都是不需要反轉的。
算法2：自然是遞歸
如果題目簡化為逆序輸出這個單鏈表，那麼遞歸是很簡單的，在遞歸函數之後輸出當前元素，這樣能確保輸出第N個元素語句永遠在第N+1個遞歸函數之後執行，也就是說第N個元素永遠在第N+1個元素之後輸出，最終我們先輸出最後一個元素，然後是倒數第2個、倒數第3個，直到輸出第1個：
public static void ReverseLink2(Link head)
{
if (head.Next != null)
{
ReverseLink2(head.Next);
Console.WriteLine(head.Next.Data);
}
}
但是，現實應用中往往不是要求我們逆序輸出（不損壞原有的單鏈表），而是把這個單鏈表逆序（破壞型）。這就要求我們在遞歸的時候，還要處理遞歸後的邏輯。
首先，要把判斷單鏈表有0或1個元素這部分邏輯獨立出來，而不需要在遞歸中每次都比較一次：
public static Link ReverseLink3(Link head)
{
//if no elements or only one element exists
if (head.Next == null || head.Next.Next == null)
return head;
head.Next = ReverseLink(head.Next);
return head;
}
我們觀測到：
head.Next = ReverseLink(head.Next);
這句話的意思是為ReverseLink方法生成的逆序鏈表添加一個空表頭。
接下來就是遞歸的核心算法ReverseLink了：
static Link ReverseLink(Link head)
{
if (head.Next == null)
return head;
Link rHead = ReverseLink(head.Next);
head.Next.Next = head;
head.Next = null;
return rHead;
}
算法的關鍵就在於遞歸後的兩條語句：
head.Next.Next = head; //1
head.Next = null; //2
啥意思呢？畫個圖表示就是：
這樣，就得到了一個逆序的單鏈表，我們只用到了1個額外的變量rHead。
