两个链表生成相加链表

[编程题]两个链表生成相加链表

热度指数：2054 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

给定两个这种链表，请生成代表两个整数相加值的结果链表。

例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。

输入描述:

第一行两个整数 n 和 m，分别表示两个链表的长度。

第二行 n 个整数 ai 表示第一个链表的节点。

第三行 m 个整数 bi 表示第二个链表的节点。

输出描述:

输出一行整数表示结果链表。

示例1

输入

3 2
9 3 7
6 3

输出

1 0 0 0

备注:

算法知识视频讲解

Java

myorange

时间复杂度O(n+m)，空间复杂度O(1)

1 先反转链表

2 计算结果链表

3 反转结果链表

4 输出

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        Node head1 = input(sc, n);
        Node head2 = input(sc, m);
        head1 = reverse(head1);
        head2 = reverse(head2);
        Node ret = null, p = null;
        int c = 0; // 进位
        Node p1 = head1;
        Node p2 = head2;
        while(p1 != null || p2 != null || c != 0) {
            int sum = (p1 == null ? 0: p1.val) + (p2 == null ? 0: p2.val) + c;
            if (sum >= 10) {
                sum -= 10;
                c = 1;
            } else {
                c = 0;
            }
            if (ret == null) {
                ret = p = new Node(sum);
            } else {
                p.next = new Node(sum);
                p = p.next;
            }
            p1 = p1 == null ? null: p1.next;
            p2 = p2 == null ? null: p2.next;
        }
        p = ret = reverse(ret);
        StringBuilder cache = new StringBuilder();
        while(p != null) {
            cache.append(p.val).append(" ");
            p = p.next;
        }
        if (cache.length() > 0) {
            cache.deleteCharAt(cache.length() - 1);
        }
        System.out.println(cache);
    }

    private static Node input(Scanner sc, int n) {
        Node head = null, p = null;
        for (int i = 0; i < n; ++i) {
            if (head == null) {
                head = p = new Node(sc.nextInt());
            } else {
                p.next = new Node(sc.nextInt());
                p = p.next;
            }
        }
        return head;
    }

    private static Node reverse(Node head) {
        if (head == null) return null;
        Node pre = head;
        Node cur = head.next;
        Node next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        head.next = null;
        return pre;
    }
}

class Node {
    int val;
    Node next;
    Node(int val) {
        this.val = val;
    }
}

发表于 2021-08-10 17:21:36 回复(0)

Java

码海泛舟

直接套用高精度加法模板

import java.io.*;

public class Main {
    static int n, m;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);
        Node h1 = new Node(-1);
        Node p = h1;
        String[] s1 = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            p.next = new Node(Integer.parseInt(s1[i]));
            p = p.next;
        }
        h1 = h1.next;//真实头结点
        h1 = revers(h1);

        Node h2 = new Node(-1);
        p = h2;
        String[] s2 = br.readLine().split(" ");
        for (int i = 0; i < m; i++) {
            p.next = new Node(Integer.parseInt(s2[i]));
            p = p.next;
        }
        h2 = h2.next;//真实头结点
        h2 = revers(h2);

        Node h = addList(h1, h2);
        h = revers(h);
        while (h != null) {
            bw.write(h.val + " ");
            h = h.next;
        }
        bw.newLine();
        bw.flush();
    }

    private static Node addList(Node h1, Node h2) {
        Node h = new Node(-1);
        Node hh = h;
        Node p = h1, q = h2;
        int t = 0;
        while (p != null || q != null) {
            if (p != null) {
                t += p.val;
                p = p.next;
            }
            if (q != null) {
                t += q.val;
                q = q.next;
            }
            hh.next = new Node(t % 10);
            t /= 10;
            hh = hh.next;
        }
        if (t > 0) {
            hh.next = new Node(1);
            hh = hh.next;
        }
        return h.next;
    }

    private static Node revers(Node h) {
        Node cur = h;
        Node next = null;
        Node pre = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}
class Node {
    int val;
    Node next;

    public Node(int val) {
        this.val = val;
    }
}

发表于 2020-07-02 10:40:45 回复(0)

Java

牛客197105342号

代码运行了好几遍终于通过了。。。。。。。。。。

import java.util.Scanner;
import java.util.Stack;

public class Main {

    public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();
        Stack<Integer> s3 = new Stack<>();
        for (int i = 0; i < n; i++) {
            s1.push(sc.nextInt());
        }
        for (int i = 0; i < m; i++) {
            s2.push(sc.nextInt());
        }
        int carry =0;
        while(!s2.isEmpty()||!s1.isEmpty()){

            int a = s1.isEmpty()?0:(int)s1.pop();
            int b = s2.isEmpty()?0:(int)s2.pop();

            int c = a+b+carry;
            s3.push(c%10);
            carry = c / 10;

        }
        if(carry!=0) s3.push(carry);
        while (!s3.isEmpty()) {
            System.out.print(s3.pop()+" ");
        }
        
    }
}

发表于 2020-04-15 00:03:25 回复(0)