找出單鏈表的中間元素 算法思想：使用兩個(gè)指針first和second，只是first每次走一步，second每次走兩步：
static Link GetMiddleOne(Link head){Link first = head;Link second = head;while (first != null && first.Next != null){first = first.Next.Next;second = second.Next;}return second;}但是，這道題目有個(gè)地方需要注意，就是對于鏈表元素個(gè)數(shù)為奇數(shù)，以上算法成立。如果鏈表元素個(gè)數(shù)為偶數(shù)，那么在返回second的同時(shí)，還要返回second.Next也就是下一個(gè)元素，它倆都算是單鏈表的中間元素。 下面是加強(qiáng)版的算法，無論奇數(shù)偶數(shù)，一概通殺：
static void Main(string[] args){Link head = GenerateLink();bool isOdd = true;Link middle = GetMiddleOne(head, ref isOdd);if (isOdd){Console.WriteLine(middle.Data);}else{Console.WriteLine(middle.Data);Console.WriteLine(middle.Next.Data);}Console.Read();}static Link GetMiddleOne(Link head, ref bool isOdd){Link first = head;Link second = head;while (first != null && first.Next != null){first = first.Next.Next;second = second.Next;}if (first != null)isOdd = false;return second;}兩個(gè)不交叉的有序鏈表的合并 有兩個(gè)有序鏈表，各自內(nèi)部是有序的，但是兩個(gè)鏈表之間是無序的。 算法思路：當(dāng)然是循環(huán)逐項(xiàng)比較兩個(gè)鏈表了，如果一個(gè)到了頭，就不比較了，直接加上去。 注意，對于2個(gè)元素的Data相等（僅僅是Data相等哦，而不是相同的引用），我們可以把它視作前面的Data大于后面的Data，從而節(jié)省了算法邏輯。
static Link MergeTwoLink(Link head1, Link head2){Link head = new Link(null, Int16.MinValue);Link PRe = head;Link curr = head.Next;Link curr1 = head1;Link curr2 = head2;//compare until one link run to the endwhile (curr1.Next != null && curr2.Next != null){if (curr1.Next.Data < curr2.Next.Data){curr = new Link(null, curr1.Next.Data);curr1 = curr1.Next;}else{curr = new Link(null, curr2.Next.Data);curr2 = curr2.Next;}pre.Next = curr;pre = pre.Next;}//if head1 run to the endwhile (curr1.Next != null){curr = new Link(null, curr1.Next.Data);curr1 = curr1.Next;pre.Next = curr;pre = pre.Next;}//if head2 run to the endwhile (curr2.Next != null){curr = new Link(null, curr2.Next.Data);curr2 = curr2.Next;pre.Next = curr;pre = pre.Next;}return head;}如果這兩個(gè)有序鏈表交叉組成了Y型呢，比如說： 這時(shí)我們需要先找出這個(gè)交叉點(diǎn)。 然后局部修改上面的算法，只要其中一個(gè)鏈表到達(dá)了交叉點(diǎn)，就直接把另一個(gè)鏈表的剩余元素都加上去。如下所示：
static Link MergeTwoLink2(Link head1, Link head2){Link head = new Link(null, Int16.MinValue);Link pre = head;Link curr = head.Next;Link intersect = GetIntersect(head1, head2);Link curr1 = head1;Link curr2 = head2;//compare until one link run to the intersectwhile (curr1.Next != intersect && curr2.Next != intersect){if (curr1.Next.Data < curr2.Next.Data){curr = new Link(null, curr1.Next.Data);curr1 = curr1.Next;}else{curr = new Link(null, curr2.Next.Data);curr2 = curr2.Next;}pre.Next = curr;pre = pre.Next;}//if head1 run to the intersectif (curr1.Next == intersect){while (curr2.Next != null){curr = new Link(null, curr2.Next.Data);curr2 = curr2.Next;pre.Next = curr;pre = pre.Next;}}//if head2 run to the intersectelse if (curr2.Next == intersect){while (curr1.Next != null){curr = new Link(null, curr1.Next.Data);curr1 = curr1.Next;pre.Next = curr;pre = pre.Next;}}return head;}兩個(gè)單鏈表相交，計(jì)算相交點(diǎn) 分別遍歷兩個(gè)單鏈表，計(jì)算出它們的長度M和N，假設(shè)M比N大，則長度M的鏈表先前進(jìn)M-N，然后兩個(gè)鏈表同時(shí)以步長1前進(jìn)，前進(jìn)的同時(shí)比較當(dāng)前的元素，如果相同，則必是交點(diǎn)。
public static Link GetIntersect(Link head1, Link head2){Link curr1 = head1;Link curr2 = head2;int M = 0, N = 0;//goto the end of the link1while (curr1.Next != null){curr1 = curr1.Next;M++;}//goto the end of the link2while (curr2.Next != null){curr2 = curr2.Next;N++;}//return to the begining of the linkcurr1 = head1;curr2 = head2;if (M > N){for (int i = 0; i < M – N; i++)curr1 = curr1.Next;}else if (M < N){for (int i = 0; i < N – M; i++)curr2 = curr2.Next;}while (curr1.Next != null){if (curr1 == curr2){return curr1;}curr1 = curr1.Next;curr2 = curr2.Next;}return null;}單鏈表排序 無外乎是冒泡、選擇、插入等排序方法。關(guān)鍵是交換算法，需要額外考慮。本題的排序過程中，我們可以在外層和內(nèi)層循環(huán)里面，捕捉到pre1和pre2，然后進(jìn)行交換，而無需每次交換又要遍歷一次單鏈表。在實(shí)踐中，我發(fā)現(xiàn)冒泡排序和選擇排序都要求內(nèi)層循環(huán)從鏈表的末尾向前走，這明顯是不合時(shí)宜的。所以我最終選擇了插入排序算法，如下所示： 先給出基于數(shù)組的算法：
static int[]InsertSort(int[] arr){for(int i=1; i<arr.Length;i++){for(int j =i; (j>0)&&arr[j]<arr[j-1];j–){arr[j]=arr[j]^arr[j-1];arr[j-1]=arr[j]^arr[j-1];arr[j]=arr[j]^arr[j-1];}}return arr;}仿照上面的思想，我們來編寫基于Link的算法：
public static Link SortLink(Link head){Link pre1 = head;Link pre2 = head.Next;Link min = null;for (Link curr1 = head.Next; curr1 != null; curr1 = min.Next){if (curr1.Next == null)break;min = curr1;for (Link curr2 = curr1.Next; curr2 != null; curr2 = curr2.Next){//swap curr1 and curr2if (curr2.Data < curr1.Data){min = curr2;curr2 = curr1;curr1 = min;pre1.Next = curr1;curr2.Next = curr1.Next;curr1.Next = pre2;//if exchange element n-1 and n, no need to add reference from pre2 to curr2, because they are the same oneif (pre2 != curr2)pre2.Next = curr2;}pre2 = curr2;}pre1 = min;pre2 = min.Next;}return head;}值得注意的是，很多人的算法不能交換相鄰兩個(gè)元素，這是因?yàn)閜re2和curr2是相等的，如果此時(shí)還執(zhí)行pre2.Next = curr2; 會(huì)造成一個(gè)自己引用自己的環(huán)。 交換指針很是麻煩，而且效率也不高，需要經(jīng)常排序的東西最好不要用鏈表來實(shí)現(xiàn)，還是數(shù)組好一些。
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
