Java 中用链表表示的数字相加

2024年9月26日 | 阅读时长 8 分钟

这是一个非常有趣的问题，经常出现在 Google、Amazon、TCS、Accenture 等顶级 IT 公司的面试中。通过解决这个问题，面试官希望检验面试者的逻辑能力、批判性思维和解决问题的能力。因此，在本节中，我们将用不同的方法和逻辑来解决 如何在 Java 中将链表表示的数字相加。同时，我们还将为此创建 Java 程序。

问题陈述

给出两个链表。每个链表代表一个数字。任务是找出每个链表所表示的数字之和。答案必须以链表的形式给出。请看以下示例。

示例 1

输入

L1 = 7 -> 9 -> 0 -> 5 -> 9 -> 1 -> 2 -> NULL

L2 = 5 -> 3 -> 8 -> 4 -> 3 -> 6 -> 4 -> NULL

输出: 1 -> 3 -> 2 -> 9 -> 0 -> 2 -> 7 -> 6 -> NULL

解释: 链表 L1 表示的数字是 7905912，链表 L2 表示的数字是 5384364，它们的和是 7905912 + 5384364 = 13290276。

示例 2

输入

L1 = 9 -> 8 -> 0 -> 4 -> 3 -> 6 -> 2 -> NULL

L2 = 8 -> 5 -> 7 -> NULL

输出: 9 -> 8 -> 0 -> 5 -> 2 -> 1 -> 9 -> NULL

解释: 链表 L1 表示的数字是 9804362，链表 L2 表示的数字是 857，它们的和是 9804362 + 857 = 9805219。

问题解决方案

方法：使用递归

我们知道两个数字的和可以通过从右到左相加数字来找到。因此，需要反转给定的链表。但是，我们不会真正反转链表。我们将使用递归来模拟相同的操作。我们将进行我们在小学学到的基本加法。在找到和之后，构建一个新的链表来显示和。下面提到了相同的图示。

文件名: NumberSumLinkedList.java

public class NumberSumLinkedList 
{

// h1 will point to the first node of the first linked list
static LinkedListNode h1;
static LinkedListNode h2;

// class for creating the nodes of the linked list
static class LinkedListNode 
{

int val;
LinkedListNode nxt;

// constructor of the LinkedListNode class
LinkedListNode(int d) 
{
val = d;
nxt = null;
}
}

// The method adds the value of the element of the two linked list f & s
// and displays it
void addTwoLinkedLists(LinkedListNode f, LinkedListNode s) 
{
LinkedListNode begin1 = new LinkedListNode(0);
begin1.nxt = f;
LinkedListNode begin2 = new LinkedListNode(0);
begin2.nxt = s;

addPrecedingZeros(begin1, begin2);
LinkedListNode res = new LinkedListNode(0);
if (addTwoNodes(begin1.nxt, begin2.nxt, res) == 1) 
{
LinkedListNode nde = new LinkedListNode(1);
nde.nxt = res.nxt;
res.nxt = nde;
}
displayLinkedList(res.nxt);
}

// Adds the linked list and returing the carrylists and returning the carry 
private int addTwoNodes(LinkedListNode l1, LinkedListNode l2, LinkedListNode res) 
{
if (l1 == null) 
{
return 0;
}
int num = l1.val + l2.val + addTwoNodes(l1.nxt, l2.nxt, res);
LinkedListNode nde = new LinkedListNode(num % 10);
nde.nxt = res.nxt;
res.nxt = nde;
return num / 10;
}

// Appending the preceding zeros in the case where one list has more nodes as 
//compared to others
private void addPrecedingZeros(LinkedListNode s1, LinkedListNode s2) 
{
LinkedListNode nxt1 = s1.nxt;
LinkedListNode nxt2 = s2.nxt;
while (nxt1 != null && nxt2 != null) 
{
nxt1 = nxt1.nxt;
nxt2 = nxt2.nxt;
}

// first linked has lesser number of elements
// therefore zero will be appended to the first linked list
if (nxt1 == null && nxt2 != null) 
{
while (nxt2 != null) 
{
LinkedListNode nde = new LinkedListNode(0);
nde.nxt = s1.nxt;
s1.nxt = nde;
nxt2 = nxt2.nxt;
}
} 


// second linked has lesser number of elements
// therefore zero will be appended to the second linked list
else if (nxt2 == null && nxt1 != null) 
{
while (nxt1 != null) 
{
LinkedListNode nde = new LinkedListNode(0);
nde.nxt = s2.nxt;
s2.nxt = nde;
nxt1 = nxt1.nxt;
}
}
}

// A method for printing the linked list 
void displayLinkedList(LinkedListNode h) 
{
while (h != null) 
{
System.out.print(h.val + " ");
h = h.nxt;
}
System.out.println(" ");
}

// main method
public static void main(String[] argvs) 
{
// creating an object of the class NumberSumLinkedList
NumberSumLinkedList list = new NumberSumLinkedList();

// creating the first list
list.h1 = new LinkedListNode(7);
list.h1.nxt = new LinkedListNode(9);
list.h1.nxt.nxt = new LinkedListNode(0);
list.h1.nxt.nxt.nxt = new LinkedListNode(5);
list.h1.nxt.nxt.nxt.nxt = new LinkedListNode(9);
list.h1.nxt.nxt.nxt.nxt.nxt = new LinkedListNode(1);
list.h1.nxt.nxt.nxt.nxt.nxt.nxt = new LinkedListNode(2);
System.out.print("First List is ");
list.displayLinkedList(h1);

// creating the second list
list.h2 = new LinkedListNode(5);
list.h2.nxt = new LinkedListNode(3);
list.h2.nxt.nxt = new LinkedListNode(8);
list.h2.nxt.nxt.nxt = new LinkedListNode(4);
list.h2.nxt.nxt.nxt.nxt = new LinkedListNode(3);
list.h2.nxt.nxt.nxt.nxt.nxt = new LinkedListNode(6);
list.h2.nxt.nxt.nxt.nxt.nxt.nxt = new LinkedListNode(4);
System.out.print("Second List is ");
list.displayLinkedList(h2);

System.out.print("Resultant List is ");

// adding the two lists and diplaying the result 
list.addTwoLinkedLists(h1, h2);

System.out.println("\n");


// creating the first list
list.h1 = new LinkedListNode(9);
list.h1.nxt = new LinkedListNode(8);
list.h1.nxt.nxt = new LinkedListNode(0);
list.h1.nxt.nxt.nxt = new LinkedListNode(4);
list.h1.nxt.nxt.nxt.nxt = new LinkedListNode(3);
list.h1.nxt.nxt.nxt.nxt.nxt = new LinkedListNode(6);
list.h1.nxt.nxt.nxt.nxt.nxt.nxt = new LinkedListNode(2);
System.out.print("First List is ");
list.displayLinkedList(h1);

// creating the second list
list.h2 = new LinkedListNode(8);
list.h2.nxt = new LinkedListNode(5);
list.h2.nxt.nxt = new LinkedListNode(7);
System.out.print("Second List is ");
list.displayLinkedList(h2);

System.out.print("Resultant List is ");

// adding the two lists and diplaying the result 
list.addTwoLinkedLists(h1, h2);
}


}

输出

First List is 7 9 0 5 9 1 2  
Second List is 5 3 8 4 3 6 4  
Resultant List is 1 3 2 9 0 2 7 6  


First List is 9 8 0 4 3 6 2  
Second List is 8 5 7  
Resultant List is 9 8 0 5 2 1 9

复杂度分析: 由于加法需要遍历两个链表。因此，程序的时间复杂度是 O(a + b)，其中 a 是第一个链表中元素的总数，b 是第二个链表中元素的总数。程序的空间复杂度也是 O(a + b)，因为我们还需要存储结果链表。

方法: 使用迭代

在这个方法中，我们将使用一个栈来存储两个链表的元素。我们知道栈的工作方式是后进先出 (LIFO)。因此，最后一个节点将首先被弹出。对从两个链表中弹出的元素执行加法操作。

文件名: MajorityEle1.java

// important import statement 
import java.util.Stack;

public class NumberSumLinkedList1 
{

// h1 will point to the first node of the first linked list
static LinkedListNode h1;
static LinkedListNode h2;

// class for creating the nodes of the linked list
static class LinkedListNode 
{

int val;
LinkedListNode nxt;

// constructor of the LinkedListNode class
LinkedListNode(int d) 
{
val = d;
nxt = null;
}
}

// The method adds the value of the element of the two linked list l1 & l2
// and displays it
void addTwoLinkedLists(LinkedListNode l1, LinkedListNode l2) 
{

// stack for adding elements of the first linked list
Stack<Integer> stk1 = new Stack<Integer>();

// stack for adding elements of the second linked list
Stack<Integer> stk2 = new Stack<Integer>();

// stack for adding elements of the resultant linked list
Stack<Integer> resStack = new Stack<Integer>();

// adding elements of the first linked list to the stack
while(l1 != null)
{
    stk1.push(l1.val);
    l1 = l1.nxt;
}


// adding elements of the second linked list to the stack
while(l2 != null)
{
    stk2.push(l2.val);
    l2 = l2.nxt;
}


// computing sizes of the stacks stk1 and stk2
int s1 = stk1.size();
int s2 = stk2.size();

int carry = 0;

// add the elements of linked list l1 and l2
while(s1 != 0 && s2 != 0)
{
    int a = stk1.pop();
    int b = stk2.pop();
    int dig = (a + b + carry) % 10;
    carry = (a + b + carry) / 10;
    
    // adding elements of the resultant linked list to the stack
    resStack.push(dig);
    s1 = s1 - 1;
    s2 = s2 - 1;
}

// when the size of the first linked list is 
// more than the second linked list
while(s1 != 0)
{
    int a = stk1.pop();
    int dig = (a + carry) % 10;
    carry = (a + carry) / 10;
    resStack.push(dig);
    s1 = s1 - 1;
}


// when the size of the second linked list is 
// more than the first linked list
while(s2 != 0)
{
    int a = stk2.pop();
    int dig = (a + carry) % 10;
    carry = (a + carry) / 10;
    resStack.push(dig);
    s2 = s2 - 1;
    
    System.out.print("vbn ");
}

// if carry is not zero and 
// all the elements of both the linked lists
// are processed, then carry should be pushed 
// in the result stack
if(carry != 0)
{
    resStack.push(carry);
}


// computing the size of the stack resStack
int resStackSize = resStack.size();

LinkedListNode res = new LinkedListNode(0);
LinkedListNode temp = res;

// loop for creating the resultant linked list
// from the resultant stack
while(resStackSize != 0)
{
    temp.nxt = new LinkedListNode(resStack.pop());
    resStackSize = resStackSize - 1;
    temp = temp.nxt;
}

// method for displaying the linked list
displayLinkedList(res.nxt);

}



// A method for printing the linked list 
void displayLinkedList(LinkedListNode h) 
{
while (h != null) 
{
System.out.print(h.val + " ");
h = h.nxt;
}
System.out.println(" ");
}

// main method
public static void main(String[] argvs) 
{
// creating an object of the class NumberSumLinkedList1
NumberSumLinkedList1 list = new NumberSumLinkedList1();

// creating the first list
list.h1 = new LinkedListNode(7);
list.h1.nxt = new LinkedListNode(9);
list.h1.nxt.nxt = new LinkedListNode(0);
list.h1.nxt.nxt.nxt = new LinkedListNode(5);
list.h1.nxt.nxt.nxt.nxt = new LinkedListNode(9);
list.h1.nxt.nxt.nxt.nxt.nxt = new LinkedListNode(1);
list.h1.nxt.nxt.nxt.nxt.nxt.nxt = new LinkedListNode(2);
System.out.print("First List is ");
list.displayLinkedList(h1);

// creating the second list
list.h2 = new LinkedListNode(5);
list.h2.nxt = new LinkedListNode(3);
list.h2.nxt.nxt = new LinkedListNode(8);
list.h2.nxt.nxt.nxt = new LinkedListNode(4);
list.h2.nxt.nxt.nxt.nxt = new LinkedListNode(3);
list.h2.nxt.nxt.nxt.nxt.nxt = new LinkedListNode(6);
list.h2.nxt.nxt.nxt.nxt.nxt.nxt = new LinkedListNode(4);
System.out.print("Second List is ");
list.displayLinkedList(h2);

System.out.print("Resultant List is ");

// adding the two lists and diplaying the result 
list.addTwoLinkedLists(h1, h2);

System.out.println("\n");


// creating the first list
list.h1 = new LinkedListNode(9);
list.h1.nxt = new LinkedListNode(8);
list.h1.nxt.nxt = new LinkedListNode(0);
list.h1.nxt.nxt.nxt = new LinkedListNode(4);
list.h1.nxt.nxt.nxt.nxt = new LinkedListNode(3);
list.h1.nxt.nxt.nxt.nxt.nxt = new LinkedListNode(6);
list.h1.nxt.nxt.nxt.nxt.nxt.nxt = new LinkedListNode(2);
System.out.print("First List is ");
list.displayLinkedList(h1);

// creating the second list
list.h2 = new LinkedListNode(8);
list.h2.nxt = new LinkedListNode(5);
list.h2.nxt.nxt = new LinkedListNode(7);
System.out.print("Second List is ");
list.displayLinkedList(h2);

System.out.print("Resultant List is ");

// adding the two lists and diplaying the result 
list.addTwoLinkedLists(h1, h2);
}


}

输出

First List is 7 9 0 5 9 1 2  
Second List is 5 3 8 4 3 6 4  
Resultant List is 1 3 2 9 0 2 7 6  


First List is 9 8 0 4 3 6 2  
Second List is 8 5 7  
Resultant List is 9 8 0 5 2 1 9

复杂度分析: 程序的时间和空间复杂度与上述相同。

下一个主题Java 中数组中的多数元素

← 上一个下一个 →

Java 中用链表表示的数字相加

问题陈述

问题解决方案

方法：使用递归

方法: 使用迭代

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java 程序

Java 中用链表表示的数字相加

问题陈述

问题解决方案

方法：使用递归

方法: 使用迭代

相关帖子

创建和显示循环链表的 Java 程序

查找字符频率的 Java 程序

Java 创建 N 个节点的循环链表并计算节点数的程序

How to Print ASCII Value in Java

Java 中检查 n 及其两倍是否存在

查找二叉树中最大距离节点的 Java 程序

Java 中的旋转列表

矩阵转置的 Java 程序

Java 创建和显示单链表的程序

从循环链表中删除重复元素的 Java 程序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器