两个链表生成相加链表

# include <bits/stdc++.h>
using namespace std;

struct list_node{
    int val;
    struct list_node * next;
};

list_node * input_list(int n)
{
    int val;
    list_node * phead = new list_node();
    list_node * cur_pnode = phead;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &val);
        if (i == 1) {
            cur_pnode->val = val;
            cur_pnode->next = NULL;
        }
        else {
            list_node * new_pnode = new list_node();
            new_pnode->val = val;
            new_pnode->next = NULL;
            cur_pnode->next = new_pnode;
            cur_pnode = new_pnode;
        }
    }
    return phead;
}

int get_length(list_node *head){
    int l = 0;
    while(head){
        l++;
        head = head->next;
    }
    return l;
}

list_node * add(list_node *head1, list_node *head2){
    list_node *p1 = head1, *p2 = head2;
    int s = 0, t=0;
    while(p1 && p2){
        s = p1->val + p2->val + t;
        p1->val = s%10;
        t = s/10;
        if(p1->next==NULL && t){
            list_node *q = new list_node();
            q->val = t;
            p1->next = q;
            t = 0;
            return head1;
        }
        p1 = p1->next;
        p2 = p2->next;
    }
    while(p1){
        s = p1->val + t;
        p1->val = s%10;
        t = s/10;
        if(p1->next==NULL && t){
            list_node *q = new list_node();
            q->val = t;
            p1->next = q;
            return head1;
        }
        p1 = p1->next;
    }
    return head1;
}

list_node * reverse_list(list_node *head){
    list_node *L=nullptr, *p = head;
    while(head){
        p = head->next;
        head->next = L;
        L = head;
        head = p;
    }
    return L;
}

list_node * add_list(list_node * head1, list_node * head2)
{
    int n = get_length(head1);
    int m = get_length(head2);
    if(n < m)
        swap(head1, head2);
    head1 = reverse_list(head1);
    head2 = reverse_list(head2);
    list_node *head = add(head1, head2);
    return reverse_list(head);
}

void print_list(list_node * head)
{
    while (head != NULL) {
        printf("%d ", head->val);
        head = head->next;
    }
    puts("");
}

int main ()
{
    int n, m;
    scanf("%d%d", &n, &m);
    list_node * head1 = input_list(n), * head2 = input_list(m);
    list_node * new_head = add_list(head1, head2);
    print_list(new_head);
    return 0;
}

list_node *reverseList(list_node *head){
    list_node *pre =nullptr;
    list_node *cur =head;
    list_node *temp;
    while(cur){
        temp =cur->next;
        cur->next =pre;
        pre =cur;
        cur=temp;
    }
    return pre;
}

list_node * add_list(list_node * head1, list_node * head2)
{
    //////在下面完成代码
    if(head1==nullptr)return head2;
    if(head2==nullptr)return head1;
    
    list_node *dummynode =new list_node(0);
    list_node *head =dummynode;
    
    head1 =reverseList(head1);
    head2 =reverseList(head2);
    
    int carry=0;
    while(head1!=nullptr||head2!=nullptr){
        int sum =carry;
        if(head1){
            sum+=head1->val;
            head1=head1->next;
        }
        if(head2){
            sum+=head2->val;
            head2 =head2->next;
        }
        carry=sum/10;
        head->next =new list_node(sum%10);
        head =head->next;
    }
    if(carry>0){
        head->next =new list_node(carry);
    }
    return reverseList(dummynode->next);
    
}

直接套用高精度加法模板

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;
    }
}

package Linked_List;
/*
 *case通过率为75.00%
 */
import java.util.Scanner;

class PNode2 {
	int val;
	PNode2 pre;
	PNode2 next;
	public PNode2(int data) {
		this.val = data;
	}
	public void setNode(PNode2 pre) {
		this.pre =pre;
	}
	public void setNext(PNode2 next) {
		this.next =next;
	}
}
public class Main {
	public PNode2 addLinkedList(PNode2 nrear, PNode2 mrear) {
		PNode2 ntemp =nrear;
		PNode2 mtemp =mrear;
		PNode2 head = new PNode2(0);
		PNode2 tmp =null;
		int decade=0;
		int unit =0;
		int up1=0;
		int up2=0;
		int up3=0;
		while(ntemp.pre !=null && mtemp.pre !=null) {
			up1=decade;
			decade=(ntemp.pre.val+mtemp.pre.val+up1)/10;
			unit=(ntemp.pre.val+mtemp.pre.val+up1)%10;
			PNode2 node = new PNode2(unit);
			node.setNext(tmp);
			tmp = node;
			ntemp =ntemp.pre;
			mtemp =mtemp.pre;
		}
		while(ntemp.pre !=null &&mtemp.pre ==null) {
			up2=decade;
			decade=(ntemp.pre.val+up2)/10;
			unit=(ntemp.pre.val+up2)%10;
			PNode2 node = new PNode2(unit);
			node.setNext(tmp);
			tmp = node;
			ntemp =ntemp.pre;
		}
		while(ntemp.pre ==null &&mtemp.pre !=null) {
			up3=decade;
			decade=(mtemp.pre.val+up3)/10;
			unit=(mtemp.pre.val+up3)%10;
			PNode2 node = new PNode2(unit);
			node.setNext(tmp);
			tmp = node;
			mtemp =mtemp.pre;
		}
		head.setNext(tmp);
		head.val =decade;
		return head;
	}
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		//LinkedList1
		PNode2 nrear = new PNode2(0);
		PNode2 npre = null;
		int n = scan.nextInt();
		int m = scan.nextInt();
		for(int i=0;i<n;i++) {
			PNode2 new_node = new PNode2(scan.nextInt());
			new_node.setNode(npre);
			npre =new_node;
		}
		nrear.setNode(npre);
		//LinkedList2
		PNode2 mrear = new PNode2(0);
		PNode2 mpre = null;
		for(int i=0;i<m;i++) {
			PNode2 new_node = new PNode2(scan.nextInt());
			new_node.setNode(mpre);
			mpre =new_node;
		}
		mrear.setNode(mpre);
		Main mall = new Main();
		PNode2 head_new =mall.addLinkedList(nrear, mrear);
		PNode2  new_temp=head_new;
		if(new_temp.val !=0) {
			System.out.print(head_new.val+" ");
		}
		while(new_temp.next !=null) {
			System.out.print(new_temp.next.val+" ");
			new_temp = new_temp.next;
		}
	}
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {

    public static class Node {

        public int value;
        public Node next;

        public Node(int value) {
            this.value = value;
        }
    }
    
    public static Node addLists1(Node head1, Node head2) {
        head1 = reverseList(head1);
        head2 = reverseList(head2);
        int sum = 0;
        int n1 = 0;
        int n2 = 0;
        int carry = 0;
        Node cur1 = head1;
        Node cur2 = head2;
        Node node = null;
        Node next = null;
        while (cur1 != null || cur2 != null) {
            n1 = cur1 == null ? 0 : cur1.value;
            n2 = cur2 == null ? 0 : cur2.value;
            sum = n1 + n2 + carry;
            node = new Node(sum % 10);
            node.next = next;
            next = node;
            carry = sum / 10;
            cur1 = cur1 == null ? null : cur1.next;
            cur2 = cur2 == null ? null : cur2.next;
        }
        if (carry == 1) {
            node = new Node(1);
            node.next = next;
        }
        reverseList(head1);
        reverseList(head2);
        return node;
    }
    
    private static Node reverseList(Node head) {
        Node pre = null;
        Node next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
    
    public static Node listGenerator(int length, String[] numbers) {
        Node head = new Node(Integer.parseInt(numbers[0]));
        Node cur = head;
        for (int i = 1; i < length; i++) {
            cur.next = new Node(Integer.parseInt(numbers[i]));
            cur = cur.next;
        }
        cur.next = null;
        return head;
    }
    
    public static void printList(Node head) {
        while (head != null) {
            System.out.print(head.value +" ");
            head = head.next;
        }
        System.out.println();
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] parameters = bufferedReader.readLine().split(" ");
        int n = Integer.parseInt(parameters[0]);
        int m = Integer.parseInt(parameters[1]);
        String[] numbers1 = bufferedReader.readLine().split(" ");
        String[] numbers2 = bufferedReader.readLine().split(" ");
        Node head1 = listGenerator(n, numbers1);
        Node head2 = listGenerator(m, numbers2);
        Node head = addLists1(head1, head2);
        printList(head);
    }
}

时间复杂度太大，只能通过80%的用例

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

class ListNode{
    int value;
    ListNode next;
    public ListNode(int value){
        this.value = value;
    }

    static ListNode convertArrayToLink(int[] arr){
        ListNode dummyNode = new ListNode(-1);
        ListNode rear = dummyNode;
        for (int i = 0; i < arr.length; i++) {
            rear.next = new ListNode(arr[i]);
            rear = rear.next;
        }
        return dummyNode.next;
    }

    static void printLink(ListNode head){
        while (head != null){
            System.out.print(head.value + " ");
            head = head.next;
        }
    }
}

public class Main {
    ListNode addLists(ListNode head1, ListNode head2){
        Stack<Integer> num1 = linkToStack(head1);
        Stack<Integer> num2 = linkToStack(head2);
        Stack<Integer> sum = new Stack<>();

        int carry = 0;
        while (!num1.isEmpty() && !num2.isEmpty()){
            int elementFromNum1 = num1.pop();
            int elementFromNum2 = num2.pop();
            sum.push((elementFromNum1 + elementFromNum2 + carry) % 10);
            carry = (elementFromNum1 + elementFromNum2 + carry) / 10;
        }

        while (!num1.isEmpty()){
            int element = num1.pop();
            sum.push((element + carry) % 10);
            carry = (element + carry) / 10;
        }

        while (!num2.isEmpty()){
            int element = num2.pop();
            sum.push((element + carry) % 10);
            carry = (element + carry) / 10;
        }

        if (carry == 1){
            sum.push(carry);
        }

        ListNode dummyNode = new ListNode(-1);
        ListNode rearNode = dummyNode;
        while (!sum.isEmpty()){
            ListNode newNode = new ListNode(sum.pop());
            rearNode.next = newNode;
            rearNode = rearNode.next;
        }
        return dummyNode.next;
    }

    Stack<Integer> linkToStack(ListNode head){
        Stack<Integer> stack = new Stack<>();
        while (head != null){
            stack.push(head.value);
            head = head.next;
        }
        return stack;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        bufferedReader.readLine();
        String[] arrayInputs1 = bufferedReader.readLine().split(" ");
        String[] arrayInputs2 = bufferedReader.readLine().split(" ");
        int[] sum1 = new int[arrayInputs1.length];
        for (int i = 0; i < arrayInputs1.length; ++i){
            sum1[i] = Integer.valueOf(arrayInputs1[i]);
        }
        int[] sum2 = new int[arrayInputs2.length];
        for(int i = 0; i < arrayInputs2.length; ++i){
            sum2[i] = Integer.valueOf(arrayInputs2[i]);
        }
        ListNode.printLink(new Main().addLists(ListNode.convertArrayToLink(sum1), ListNode.convertArrayToLink(sum2)));
    }
}