两个单链表生成相加链表【Java实现】

小半 • 2023年2月2日上午10:14 • 后端开发 • 阅读 191

题目：

假设链表中每一个节点的值都在0~9之间，那么链表整体就可以代表一个整数。

例如：9—3—7，就可以代表整数937

链表1为9—>3—>7，链表2为 6—>3，最后生成新的结果链表为 1—>0—>0—>0

方法一：

将两个链表分别转换为两个整数，然后再相加

此处用到的方法：

（1）如何将单链表转换成数字，9—>3—>7转换成937

String str1 = “”;

while (head1 != null) {

str1 += head1.value; //先将所有值放入字符串中

head1 = head1.next;

}

int a1 = Integer.parseInt(str1); //将字符串类型转换为int类型

（2）如何把结果，从低位到高位插入到新的链表中（用的头插法）

例如 sum= 937

先对 10 求余，得到各位数 7，然后在除10，sum变为93。重复操作知道sum=0

代码实现：

    //两个链表相加  链表1为9—>3—>7，链表2为 6—>3，最后生成新的结果链表为 1—>0—>0—>0
    public static Node addList(Node head1, Node head2) {
        //先分别找出两个链表所代表的整数
        String str1 = "";
        String str2 = "";
        while (head1 != null) {
            str1 += head1.value;
            head1 = head1.next;
        }
        while (head2 != null) {
            str2 += head2.value;
            head2 = head2.next;
        }
        int a1 = Integer.parseInt(str1);
        int a2 = Integer.parseInt(str2);
        int sum = a1 + a2;

        //将sum生成一个新的链表  这里要考虑如何取出一个数的 第一位 第二位 。。。
        Node newHead=new Node(0);
        while (sum != 0) {
            int tmp = sum % 10;
            sum = sum/10;
            Node cur = new Node(tmp);
            if (newHead.next == null) {
                newHead.next = cur;
            } else {
                cur.next = newHead.next;
                newHead.next = cur;
            }
        }
        return newHead.next;
    }

另外在生成新链表的时候也可以用尾插法，代码如下：

    public static Node addList1(Node head1, Node head2) {
        //先分别找出两个链表所代表的整数
        String str1 = "";
        String str2 = "";
        while (head1 != null) {
            str1 += head1.value;
            head1 = head1.next;
        }
        while (head2 != null) {
            str2 += head2.value;
            head2 = head2.next;
        }
        int a1 = Integer.parseInt(str1);
        int a2 = Integer.parseInt(str2);
        int sum = a1 + a2;
        String s = String.valueOf(sum);
        System.out.println(s);

        //将sum生成一个新的链表  这里要考虑如何取出一个数的 第一位 第二位 。。。
        Node head = null;
        Node cur = null;
        Node node = null;
        //尾插法 遍历字符串 然后进行插入
        for (int i = 0; i < s.length(); i++) {
            node = new Node(Integer.parseInt(s.substring(i,i+1)));
            if (head == null){
                head = node; //保存头节点，用于return返回
                cur = node; 
            } else {
                cur.next = node;
                cur = cur.next;
            }
        }
        return head;
    }

补充知识：关于单链表的头插法和尾插法