链表相加-Java-笔试题

题目：给定两个链表，分别表示两个非负整数，它们的数字逆序存储在链表中，且每个结点只存储一个数字，计算两个数的和，并且返回和的链表头指针；
例如：输入：2->4->3、5->6->4，输出：7->0->8

算法思想：算法本身不难，和列竖式相加类似，两个链表中各取出一个结点数字，求和后，根据所求结果value，若有进位则 carry = value / 10，下次求和时使用，若无进位，则由value生成一个新的结点，并采用尾插法加入到新链表的头结点后面；若其中一个链表较长，则进一步处理较长的链表，较长的结点加入新链表的尾端，可能还要考虑进位carry；还要再考虑最后一位还有没有进位数carry，若有，则生成一个新结点加入到新链表尾端；
随机生成两个求和链表时，我采用头插法，这样使得数字结点插入之后，返回的链表正好是逆序存储的；

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

import java.util.Random;
/**
* @author neuHenry
*/
public class AddNumWithLink {
public static void main(String[] args) {
Random random = new Random(10);
// 初始化两个链表
Node header1 = null;
for (int i = 0; i < 7; i++) {
Node node = new Node(random.nextInt(10));
node.next = header1; // 这里采用头插法
header1 = node;
}
// 输出链表1的节点值
print(header1);
Node header2 = null;
for (int i = 0; i < 8; i++) {
Node node = new Node(random.nextInt(10));
node.next = header2;
header2 = node;
}
// 输出链表2的节点值
print(header2);
Node result = null;
result = add(header1, header2);
// 输出求和后新链表的节点值
print(result.next);
}
/**
* 打印输出链表
* @param node 链表的头结点
*/
public static void print(Node node) {
while (node != null) {
System.out.print(node.value + " ");
node = node.next;
}
System.out.println();
}
/**
* 两个链表相加
* @param link1 链表1的头结点
* @param link2 链表2的头结点
* @return
两链表相加后所得新链表的头结点
*/
public static Node add(Node link1, Node link2) {
Node sum = new Node();
// 所求新链表的头结点
Node pTail = sum;
Node p1 = link1, p2 = link2;
Node cur;
int carry = 0;
int temp;
while (p1 != null && p2 != null) {
temp = p1.value + p2.value + carry;
carry = temp / 10;
// 进位值
temp = temp % 10;
// 所求新的节点值
cur = new Node(temp);
pTail.next = cur; // 这里使用尾插法
pTail = cur;
// 处理下一位
p1 = p1.next;
p2 = p2.next;
}
// 处理长度较长的链表，将较长的链表添加到新链表中
Node p = (p1 != null) ? p1 : p2;
while (p != null) {
temp = p.value + carry;
carry = temp / 10;
temp = temp % 10;
cur = new Node(temp);
pTail.next = cur;
pTail = cur;
p = p.next;
}
// 处理可能存在的进位
if (carry != 0) {
cur = new Node(carry);
pTail.next = cur;
pTail = cur;
}
return sum;
}
}

程序运行结果如下：

若还有好的建议，还望不吝赐教！

最后

以上就是忧伤汉堡为你收集整理的链表相加-Java-笔试题的全部内容，希望文章能够帮你解决链表相加-Java-笔试题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。