算法篇--链表求和问题描述思考代码

96 阅读 0 评论 64 点赞

我是靠谱客的博主笑点低煎饼，最近开发中收集的这篇文章主要介绍算法篇--链表求和问题描述思考代码，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题描述

给两个链表，每个链表为一个整数的倒序，如下：

1 - 2 - 3
4 -5 - 7- 9
两个数字的结果：
321+9754= 10075

那么！请得到链表的结果为 5 - 7 - 0 - 0 - 1

思考

思路总结：两个链表肯定有一个最长的（等于情况取哪个都行），所以两个链表相加时候就用短的限制循环边界，
跳出循环后则遍历长的相加
几点注意：

1 每两个节点相加时，也要加上一次的进位信息
2 当长的链表遍历后，注意进位信息的处理

代码


public class SumLink extends BaseLink {


  

    public static Node<Integer> sumLinkWihtNode(Node<Integer> head1, Node<Integer> head2) {
        if (head1 == null || head2 == null) {
            return head1 != null ? head1 : head2;
        }
        int head1Len = lenLink(head1);
        int head2Len = lenLink(head2);
        Node<Integer> curL = head1Len >= head2Len ? head1 : head2;
        Node<Integer> curS = curL != head1 ? head1 : head2;
        int carry = 0;

        Node<Integer> realhead = curL;
        Node<Integer> lastNode = curL;

        while (curS != null) {
            int tempSum = curL.v + curS.v + carry;
            curL.v = tempSum % 10;
            carry = tempSum / 10;

            lastNode = curL;

            curL = curL.next;
            curS = curS.next;
        }

        while (curL != null) {
            int tempSum = curL.v + carry;
            curL.v = tempSum % 10;
            carry = tempSum / 10;

            lastNode = curL;

            curL = curL.next;

        }
        if(carry != 0){
            lastNode.next = new Node<>(1);
        }

        return realhead;
    }

    private static int lenLink(Node head1) {

        int ans = 0;
        while (head1 != null) {
            head1 = head1.next;
            ans++;
        }
        return ans;
    }


    public static void main(String[] args) {
        var head1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);


        head1.next = node2;
        node2.next = node3;


        Node head2 = new Node(4);
        Node node52 = new Node(5);
        Node node62 = new Node(7);
        Node node72 = new Node(9);


        head2.next = node52;
        node52.next = node62;
        node62.next = node72;


        Node<Integer> node = sumLinkWihtNode(head1, head2);
        while (node!=null){
            System.out.println(node.v);
            node = node.next;
        }
    }

}