链表模拟二进制加法及C#的实现

问题分析

1. 建链表：
   二进制数可用带头节点的单链表存储，第一个节点存储二进制数的最高位。
2. 二进制数加1运算规则：
   从低位往高位找到第一个位0的位置，把该位改为1，其后所有各位改为0。
   1010
   +1
   ————
   1100
3. 链表实现方法：从高位往低位拉，从第一个节点开始，找出最后一个值域为0的节点，把该节点值域赋为1，其后所有节点的值域赋为0。
4. 若在链表中未找到值域为0的节点，则表示该二进制数各位均为1，此时，申请一个新节点，值域置为1，头插入到原链表，其后所有节点的值域置为0

1111
+1
————
10000

算法描述

Node

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace b
{
    class Node<T>
    {
        T data;
        Node<T> next;

        public T Data { get => data; set => data = value; }
        internal Node<T> Next { get => next; set => next = value; }

        public Node()
        {
            Data = default(T);
            Next = null;
        }

        public Node(T data)
        {
            this.Data = data;
        }
    }
}

Program

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace b
{
    class Program
    {
        static void Main(string[] args)
        {
            Node<char> head = new Node<char>();
            Node<char> a1 = new Node<char>('1');

            head.Next = a1;
            BinAdd(head);
            BinAdd(head);

            while (head.Next != null)
            {
                head = head.Next;
                Console.WriteLine(head.Data);
            }
        }

        static void BinAdd(Node<char> h)
        {
            Node<char> q = h.Next;
            Node<char> l = h;

            //遍历出最后一个0
            while (q.Next != null)
            {
                if (q.Data == '0') l = q;
                q = q.Next;
            }

            //至少有一个0，找到最后一个0，改为1，后面全部置为0
            if (l != h)
            {
                l.Data = '1';
                l = l.Next;
                while (h.Next != null)
                {
                    h.Data = '0';
                    h = h.Next;
                }
            }
            //头插入1，后面全部置为0
            else
            {
                Node<char> a = new Node<char>('1'); //新建节点
                //头插入
                a.Next = h.Next;
                h.Next = a;

                h = h.Next.Next;
                while (h.Next != null)
                {
                    h.Data = '0';
                    h = h.Next;
                }
            }
        }
    }
}