LeetCode 2.Add Two Numbers-两个链表相加（JAVA）题目链接第一种解法-常规思路第二种解法-考虑各种极端情况分类辅助测试方法

83 阅读 0 评论 55 点赞

我是靠谱客的博主义气橘子，最近开发中收集的这篇文章主要介绍LeetCode 2.Add Two Numbers-两个链表相加（JAVA）题目链接第一种解法-常规思路第二种解法-考虑各种极端情况分类辅助测试方法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接

https://leetcode.com/problems/add-two-numbers/description/

题目理解：

给定两个链表，存储整形数据，返回相加的结果。第一个节点表示整数的个位，对应位置上值进行相加操作，中间涉及相加大于等于10时的进位。

需要会对链表的头结点，下一位及取值，存值，数组转换成链表存储等操作。

第一种解法-常规思路

优点：思路明了

缺点：运行速度慢，耗时

思路及源码如下，详见注释。

/**
* 两个链表相加
* @param l1 链表1
* @param l2 链表2
* @return 相加之后的结果以为链表形式返回
*/
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode pointL1 = l1;
ListNode pointL2 = l2; //新建两个指针节点指向链表头部节点
ListNode addResult = null; //新建空链表，存放相加的结果
ListNode paRes = addResult; //指向结果链表addResult的头部
int sum = 0; // 每一位相加结果存放，以及标识进位情况
//当两个链表其中一个不为null时，进行以下节点值相加，取余数，相除等操作
while (pointL1 != null || pointL2 != null) {
//当链表1不为空时，将当前节点值加到sum
if (pointL1 != null) {
sum = sum + pointL1.val;
pointL1 = pointL1.next;
}
//当链表2不为空时，将当前节点值加到sum
if (pointL2 != null) {
sum = sum + pointL2.val;
pointL2 = pointL2.next;
}
if (addResult == null) { //如果结果链表为空，则sum取模之后的结果存放到paRes中，此时指向addResult的头节点
paRes = new ListNode(sum % 10);
addResult = paRes;
} else { //如果结果链表不为空，则根据指针下一个节点操作，存放相应的结果
paRes.next = new ListNode(sum % 10);
paRes = paRes.next;
}
sum = sum / 10; //当前位置两个链表节点相加之和，有进位，进位的值
}
//判断链表最后的位想加之后，是否有进位
//sum不为0，表示最高位有进位情况，将进位赋值给addResult的下一个节点即可
if (sum != 0) {
paRes.next = new ListNode(sum);
}
return addResult;
}

其中，while循环的判断条件是pointL1 != null || pointL2 != null，如果一开始输入的参数l1为null，l2不为null，由于条件成立，每次循环都会进行循环体里面的几个if判断，虽然不成立，但是还是一步一步执行判断，速度慢。根据提交之后运行的结果看，确实比较慢，执行时间需要54ms。

第二种解法-考虑各种极端情况分类

优点：总的运行时间短

下面一种方法，会考虑各种极端情况，提前结束无谓的程序执行，并利用已有的链表，减少New操作，降低分配内存耗时，以提高效率，提交后执行时间大约才5ms

/**
*
* @param l1
* @param l2
* @return
*/
public ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
//有一个为空时，直接返回另外一个链表作为结果
if(l1 == null) {
return l2;
}
if(l2 == null) {
return l1;
}
ListNode ret = l1; //结果存放于l1。new新的链表节点分配内存耗时，此处利用已有的资源，节省时间
ListNode carry = new ListNode(0);
carry.next = l1; //最有一位相加有进位的时候
int flag = 0;
while(l1 != null && l2 != null) {
l1.val = l1.val + l2.val + flag;
flag = l1.val / 10;
l1.val = l1.val % 10;
//进位
carry = l1;
l1 = l1.next;
l2 = l2.next;
}
//结束后l2不为空，l2负载l1的后面
if(l2 != null) {
carry.next = l2;//
l1 = l2;
}
while(l1 != null) {//l1不为空
l1.val = l1.val + flag;
flag = l1.val / 10;
l1.val = l1.val % 10;
carry = l1;
l1 = l1.next;
}
if(flag > 0) {//
ListNode node = new ListNode(1);
carry.next = node;
}
return ret;
}

辅助测试方法

为了验证上面写的方法，输入两个链表之后相加的结果是否正确，用以下方法进行测试验证。

题目中给的定义链表，提取出来定义成一个ListNode类。如下：

/**
* 单链表节点定义
*/
public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) {
val = x;
}
}

定义方法outPutResult，打印输出链表各节点的值；arrToList将数组转换成链表

/**
* 打印输出链表各节点的值
*/
public void outPutResult(ListNode ls){
while (ls != null) {
System.out.print(ls.val + " ");
ls = ls.next;
}
System.out.print("n");
}
/**
* 定义方法，将一个数组转换成链表
* @param arr 输入要转换的数组
* @return 返回链表结构
*/
public ListNode arrToList(int[] arr){
ListNode result = null; //用于存放数组转成的链表
ListNode p = null; //指向result的指针
for (int i = 0; i < arr.length; i++){
if (result == null){ //如果为null，则存放为头节点
p = new ListNode(arr[i]);
result
= p;
} else {
p.next = new ListNode(arr[i]); //next指向下一个节点
p = p.next;
}
}
return result;
}

main函数调用以上方法进行测试验证

public static void main(String [] args){
int arr1[] = {2,4,8};
int arr2[] = {5,6,4,3}; //定义两个整形数组，长度可以任意
AddTwoNumbers ad = new AddTwoNumbers();
ListNode ls1 = ad.arrToList(arr1);
ListNode ls2 = ad.arrToList(arr2);
ad.outPutResult(ls1);
ad.outPutResult(ls2); //将数组转换成链接结构存储，以后后续操作
ListNode result = ad.addTwoNumbers(ls1,ls2); //调用方法addTwoNumbers对两个链接相加
ad.outPutResult(result); //打印输出相加后的链接
}