}
//recover original status, whether exists or not curr1.Next = null; return exists; }
算法3：如果两个链表的末尾元素相同，则必相交。 static bool JudgeIntersectLink3(Link head1, Link head2) {
Link curr1 = head1; Link curr2 = head2;
//goto the end of the link1 while (curr1.Next != null) {
curr1 = curr1.Next; }
//goto the end of the link2 while (curr2.Next != null) {
curr2 = curr2.Next; }
if (curr1 != curr2) return false; else
return true; }
10.两个单链表相交，计算相交点
分别遍历两个单链表，计算出它们的长度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 link1 while (curr1.Next != null) {
curr1 = curr1.Next; M++;
}
//goto the end of the link2 while (curr2.Next != null) {
curr2 = curr2.Next; N++; }
//return to the begining of the link curr1 = 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; }
11.用链表模拟大整数加法运算
例如：9>9>9>NULL + 1>NULL => 1>0>0>0>NULL
肯定是使用递归啦，不然没办法解决进位+1问题，因为这时候要让前面的节点加1，而我们的单链表是永远指向前的。
此外对于999+1=1000，新得到的值的位数（4位）比原来的两个值（1个1位，1个3位）都多，所以我们将表头的值设置为0，如果多出一位来，就暂时存放到表头。递归结束后，如果表头为1，就在新的链表外再加一个新的表头。 //head1 length > head2, so M > N
public static int Add(Link head1, Link head2, ref Link newHead, int M, int N) {
// goto the end if (head1 == null) return 0; int temp = 0; int result = 0;
newHead = new Link(null, 0); if (M > N) {
result = Add(head1.Next, head2, ref newHead.Next, M - 1, N); temp = head1.Data + result; newHead.Data = temp % 10; return temp >= 10 1 : 0; }
else // M == N {
result = Add(head1.Next, head2.Next, ref newHead.Next, M - 1, N - 1); temp = head1.Data + head2.Data + +result; newHead.Data = temp % 10; return temp >= 10 1 : 0; } }
这里假设head1比head2长，而且M、N分别是head1和head2的长度。
12.单链表排序
无外乎是冒泡、选择、插入等排序方法。关键是交换算法，需要额外考虑。第7题我编写了一个交换算法，在本题的排序过程中，我们可以在外层和内层循环里面，捕捉到pre1和pre2，然后进行交换，而无需每次交换又要遍历一次单链表。 在实践中，我发现冒泡排序和选择排序都要求内层循环从链表的末尾向前走，这明显是不合时宜的。
所以我最终选择了插入排序算法，如下所示： 先给出基于数组的算法： 代码 staticint[]
InsertSort(int[]arr) {
for(inti=1;i for(intj=i;(j>0)&&arr[j] arr[j]=arr[j]^arr[j-1]; arr[j-1]=arr[j]^arr[j-1]; arr[j]=arr[j]^arr[j-1]; } } returnarr; } 仿照上面的思想，我们来编写基于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 curr2 if (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 one if (pre2 != curr2) pre2.Next = curr2; } pre2 = curr2; } pre1 = min; pre2 = min.Next; } return head; } 值得注意的是，很多人的算法不能交换相邻两个元素，这是因为pre2和curr2是相等的，如果此时还执行pre2.Next = curr2; 会造成一个自己引用自己的环。 交换指针很是麻烦，而且效率也不高，需要经常排序的东西最好不要用链表来实现，还是数组好一些。 13.删除单链表中重复的元素 用Hashtable辅助，遍历一遍单链表就能搞定。 实践中发现，curr从表头开始，每次判断下一个元素curr.Netx是否重复，如果重复直接使用curr.Next = curr.Next.Next; 就可以删除重复元素——这是最好的算法。唯一的例外就是表尾，所以到达表尾，就break跳出while循环。 public static Link DeleteDuplexElements(Link head) { Hashtable ht = new Hashtable(); Link curr = head; while (curr != null) { if (curr.Next == null) { break; } if (ht[curr.Next.Data] != null) { curr.Next = curr.Next.Next; } else { ht[curr.Next.Data] = \ } curr = curr.Next; } return head; }
算法大全-面试题-数据结构
