算法大全（1）单链表 2

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，然后进行交换，而无需每次交换又要遍历一次单链表。

在实践中，我发现冒泡排序和选择排序都要求内层循环从链表的末尾向前走，这明显是不合时宜的。

所以我最终选择了插入排序算法，如下所示：

先给出基于数组的算法： 

代码

        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 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;
}

 

 

结语：

单链表只有一个向前指针Next，所以要使用1-2个额外变量来存储当前元素的前一个或后一个指针。

尽量用while循环而不要用for循环，来进行遍历。

哇塞，我就是不用指针，照样能“修改地址”，达到和C++同样的效果，虽然很烦~

遍历的时候，不要在while循环中head=head.Next;这样会改变原先的数据结构。我们要这么写：Link curr=head;然后curr=curr.Next;

有时我们需要临时把环切开，有时我们需要临时把单链表首尾相连成一个环。

究竟是玩curr还是curr.Next，根据不同题目而各有用武之地，没有定论，不必强求。