找出单链表的中间元素 算法思想：使用两个指针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;}但是，这道题目有个地方需要注意，就是对于链表元素个数为奇数，以上算法成立。如果链表元素个数为偶数，那么在返回second的同时，还要返回second.Next也就是下一个元素，它俩都算是单链表的中间元素。 下面是加强版的算法，无论奇数偶数，一概通杀：
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;}两个不交叉的有序链表的合并 有两个有序链表，各自内部是有序的，但是两个链表之间是无序的。 算法思路：当然是循环逐项比较两个链表了，如果一个到了头，就不比较了，直接加上去。 注意，对于2个元素的Data相等（仅仅是Data相等哦，而不是相同的引用），我们可以把它视作前面的Data大于后面的Data，从而节省了算法逻辑。
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;}如果这两个有序链表交叉组成了Y型呢，比如说： 这时我们需要先找出这个交叉点。 然后局部修改上面的算法，只要其中一个链表到达了交叉点，就直接把另一个链表的剩余元素都加上去。如下所示：
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;}两个单链表相交，计算相交点 分别遍历两个单链表，计算出它们的长度M和N，假设M比N大，则长度M的链表先前进M-N，然后两个链表同时以步长1前进，前进的同时比较当前的元素，如果相同，则必是交点。
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;}单链表排序 无外乎是冒泡、选择、插入等排序方法。关键是交换算法，需要额外考虑。本题的排序过程中，我们可以在外层和内层循环里面，捕捉到pre1和pre2，然后进行交换，而无需每次交换又要遍历一次单链表。在实践中，我发现冒泡排序和选择排序都要求内层循环从链表的末尾向前走，这明显是不合时宜的。所以我最终选择了插入排序算法，如下所示： 先给出基于数组的算法：
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;}值得注意的是，很多人的算法不能交换相邻两个元素，这是因为pre2和curr2是相等的，如果此时还执行pre2.Next = curr2; 会造成一个自己引用自己的环。 交换指针很是麻烦，而且效率也不高，需要经常排序的东西最好不要用链表来实现，还是数组好一些。
新闻热点
疑难解答
