一点一点前进...

0%

使用链表实现加法

发表于 分类于 ， Disqus：

有两个链表，代表两个数，其中每个结点都包含一个数字。每个链表是倒序排列，比如数字617，那么链表是7 -> 1 -> 6。如何求和呢？如果是正序排列，又该如何求和呢？

如果反序排列的话，链表头就是个位，接着是十位，以此类推。就和普通的手算一致，先算低位，如果大于10，需要进位，接着计算高位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private static LinkedListNode<int> AddLists(LinkedListNode<int> l1, LinkedListNode<int> l2, int carry)
{
    if (l1 == null && l2 == null && carry == 0)
    {
        return null;
    }

    int value = (l1 != null ? l1.Data : 0) + (l2 != null ? l2.Data : 0) + carry;
    var result = new LinkedListNode<int>(value % 10);
    if (l1 != null || l2 != null)
    {
        var more = AddLists(l1 != null ? l1.Next : null, l2 != null ? l2.Next : null, value >= 10 ? 1 : 0);
        result.Next = more;
    }

    return result;
}

如果链表是正序表示一个数字，该如何做呢？一个可行的方案是，反转两个链表，然后就回到了上一种情况。
这里，采用和上面类似的思想去解决这个问题，显然，比上面的问题要复杂，需要考虑的更多：

  1. 如果一个链表比另外一个长，该怎么办？比如1 -> 2 -> 3 -> 4和5 -> 6 -> 7两个链表，显然，5应该和2相加而不是1。我们可以遍历两个链表，向短的前面补充上零。
  2. 在上面那种情况下，计算结果被加到了链表的尾部，这意味着递归程序本身就可以处理进位，但是现在不行了。所以我们需要添加一些数据结构对象来处理进位。把后面的进位结果带到前面来。 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    private static LinkedListNode<int> AddLists(LinkedListNode<int> l1, LinkedListNode<int> l2)
    {
        int length1 = GetLength(l1);
        int length2 = GetLength(l2);

        if (length1 < length2)
        {
            l1 = PadList(l1, length2 - length1);
        }
        else
        {
            l2 = PadList(l2, length1 - length2);
        }

        PartialSum sum = AddListsHelper(l1, l2);

        return sum.Carry == 0 ? sum.Sum : InsertBefort(sum.Sum, 1);
    }

    private static PartialSum AddListsHelper(LinkedListNode<int> l1, LinkedListNode<int> l2)
    {
        if (l1 == null && l2 == null)
        {
            return new PartialSum();
        }

        PartialSum sum = AddListsHelper(l1.Next, l2.Next);
        int value = sum.Carry + l1.Data + l2.Data;
        var fullResult = InsertBefort(sum.Sum, value % 10);
        sum.Sum = fullResult;
        sum.Carry = value / 10;

        return sum;
    }

    private static LinkedListNode<int> InsertBefort(LinkedListNode<int> l, int p)
    {
        var node = new LinkedListNode<int>(p);
        if (l != null)
        {
            node.Next = l;
        }

        return node;
    }

    private static LinkedListNode<int> PadList(LinkedListNode<int> l, int p)
    {
        var head = l;
        for (int i = 0; i < p; i++)
        {
            LinkedListNode<int> newNode = new LinkedListNode<int>(0);
            newNode.Next = head;
            head = newNode;
        }

        return head;
    }

    private static int GetLength(LinkedListNode<int> l1)
    {
        int count = 0;
        while (l1 != null)
        {
            count++;
            l1 = l1.Next;
        }

        return count;
    }

    private class PartialSum
    {
        public LinkedListNode<int> Sum = null;
        public int Carry = 0;
    }