给定两个链表表示的整数，编写函数对这两个整数求和，并用链表形式返回结果。

75 阅读 0 评论 50 点赞

我是靠谱客的博主自由茉莉，最近开发中收集的这篇文章主要介绍给定两个链表表示的整数，编写函数对这两个整数求和，并用链表形式返回结果。，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

// Definition for singly-linked list.
// class ListNode {
// int val;
// ListNode next;
// ListNode(int x) { val = x; }
// }

class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//定义一个新链表root，一个temp的链表rear，用来当作root的指针，一个进位标志carry
ListNode root=new ListNode(0);

    //使尾节点指向头节点
    ListNode rear=root;
    //定义一个初始进位
    int carry=0;
    if (l1==null)
        return l2;
    if(l2==null)
        return l1;
    while((l1!=null)&&(l2!=null))
    {
        int rem=(l1.val+l2.val+carry)%10;
        ListNode node=new ListNode(rem);
        rear.next=node;
        carry=(l1.val+l2.val+carry)/10;
        //rear始终指向最后一个节点
        rear=node;
        l1=l1.next;
        l2=l2.next;     
    }
    // 当我这个加完后，l1或者l2有多余的则直接放到后面。
    if (l1==null)
        rear.next=l2;
    else
        rear.next=l1;
    //如果加完还有进位，如果没有进位，carry在上面就置位0，所以1就说明有进，然后进位就在后面的一个值+1，在判断是都有进位
    if (carry==1)
    {
        while(rear.next!=null)
        {
            int sum=(rear.next.val+carry);
            rear.next.val=sum%10;

            carry=sum/10;
            rear=rear.next;
        }

    //如果最后还有进位
        if (carry==1)
        {
            rear.next=new ListNode(2);
        }
    }
    return root.next;    
}

}
public class MainClass {
public static int[] stringToIntegerArray(String input) {
input = input.trim();
input = input.substring(1, input.length() - 1);
if (input.length() == 0) {
return new int[0];
}

    String[] parts = input.split(",");
    int[] output = new int[parts.length];
    for(int index = 0; index < parts.length; index++) {
        String part = parts[index].trim();
        output[index] = Integer.parseInt(part);
    }
    return output;
}

public static ListNode stringToListNode(String input) {
    // Generate array from the input
    int[] nodeValues = stringToIntegerArray(input);

    // Now convert that list into linked list
    ListNode dummyRoot = new ListNode(0);
    ListNode ptr = dummyRoot;
    for(int item : nodeValues) {
        ptr.next = new ListNode(item);
        ptr = ptr.next;
    }
    return dummyRoot.next;
}

public static String listNodeToString(ListNode node) {
    if (node == null) {
        return "[]";
    }

    String result = "";
    while (node != null) {
        result += Integer.toString(node.val) + ", ";
        node = node.next;
    }
    return "[" + result.substring(0, result.length() - 2) + "]";
}

public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    String line;
    while ((line = in.readLine()) != null) {
        ListNode l1 = stringToListNode(line);
        line = in.readLine();
        ListNode l2 = stringToListNode(line);

        ListNode ret = new Solution().addTwoNumbers(l1, l2);

        String out = listNodeToString(ret);

        System.out.print(out);
    }
}

}