合并两个已排序链表的C#代码,求指正

十一月 11, 2013 技术 @海德

问题:现有两个已排序(升序)的链表(可能含有重复值),请编写一个函数Merge将它们合并为一个有序链表(不能有重复值)。
网上一搜一大片类似的用于面试的题,在空余时间无聊研究了这个题。
其实问题都有其考查目的,为了更有特色,抛开C的指针,尝试以C#的方式解决问题;
优化策略作为解题亮的必不可少,从实际应用的出发点考量进行了如下抉择:
1、没有使用递归方案,虽然这会使代码大幅减少;因为命题中没有告知数组长度,过大的链表递归会导致栈溢出。
2、为了简化执行路径,减少不必要的赋值(或无意义操作),额外新增了几个bool标志量,虽然这会使代码量增加;但个人认为实际使用时,这样的代价是值得的。
3、为了让代码一致化更高,人为的添加了虚拟的起始节点。
4、为了防止题目中可能存在的文字游戏,对已知链表自身也要进行“重复值”检查。
5、投机语法,用了lambda表达式;所谓成也萧何、败也萧何!

最后上代码,诚恳求指正!!!

合并两个已排序链表
//节点定义
class Node
{
    public int Data;
    public Node Next;
}

//合并主函数
Node Merge(Node head1, Node head2)
{
    const int NULL = -1234567890;
    Func<Node, Node> getNextWithClean = node =>
    {
        if (node.Next != null)
        {
            Node realNext = node.Next;
            int realNextData = realNext.Data;
            bool hasJump = false;
            while (realNext.Next != null && realNext.Next.Data == realNextData)
            {
                realNext = realNext.Next;
                hasJump = true;
            }
            if (hasJump)
            {
                node.Next = realNext;
            }
            return node.Next;
        }
        else
        {
            return null;
        }
    };
    Action<Node> cleanForward = node =>
    {
        Node pointer = node;
        do
        {
            pointer = getNextWithClean(pointer);
        }
        while (pointer != null);
    };


    // Init root nodes
    head1 = new Node() { Data = NULL, Next = head1 };
    head2 = new Node() { Data = NULL, Next = head2 };

    if (head1.Next == null && head2.Next == null)
    {
        return null;
    }
    else if (head1.Next == null && head2.Next != null)
    {
        cleanForward(head2);
        return head2.Next;
    }
    else if (head2.Next == null && head1.Next != null)
    {
        cleanForward(head1);
        return head1.Next;
    }
    else
    {
        // Init result and walker
        Node resultRoot = head1, walker = head1;
        bool isWalkerInList1 = true;
        head1 = getNextWithClean(head1);
        head2 = getNextWithClean(head2);

        do
        {
            if (head1.Data < head2.Data)
            {
                if (!isWalkerInList1)
                {
                    isWalkerInList1 = true;
                    walker.Next = head1;
                }
                walker = walker.Next;
                head1 = getNextWithClean(head1);
            }
            else if (head1.Data > head2.Data)
            {
                if (isWalkerInList1)
                {
                    isWalkerInList1 = false;
                    walker.Next = head2;
                }
                walker = walker.Next;
                head2 = getNextWithClean(head2);
            }
            else
            {
                walker = walker.Next;
                head1 = getNextWithClean(head1);
                head2 = getNextWithClean(head2);
            }
        }
        while (head1 != null && head2 != null);

        // Fast link
        if (head1 == null && head2 != null)
        {
            walker.Next = head2;
            cleanForward(walker);
        }
        else if (head2 == null && head1 != null)
        {
            walker.Next = head1;
            cleanForward(walker);
        }

        return resultRoot.Next;
    }
}