两个单链表生成相加链表

50 阅读 0 评论 33 点赞

我是靠谱客的博主机智爆米花，最近开发中收集的这篇文章主要介绍两个单链表生成相加链表，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

import java.util.Stack;
//两个单链表生成相加链表
public class plusList{
//链表节点的定义
public static class Node{
public int value;
public Node next;
public Node(int data)
{
this.value=data;
}
}
//(两个数计算求和)两个单链表相加生成的链表
public static Node pluslist(Node head1,Node head2)
{
if(head1==null)
{
return head2;
}else if(head2==null){
return head1;
}else if(head1==null&&head2==null)
{
return null;
}
int num1=0;
int num2=0;
int leng1=0;
int leng2=0;
Node p=head1;
while(p!=null)
{
++leng1;
p=p.next;
}
Node q=head2;
while(q!=null)
{
++leng2;
q=q.next;
}
while(head1!=null&&leng1>=0)
{
num1+=head1.value*Math.pow(10,leng1-1);
--leng1;
head1=head1.next;
}
while(head2!=null&&leng2>=0)
{
num2+=head2.value*Math.pow(10,leng2-1);
--leng2;
head2=head2.next;
}
int sum=num1+num2;
//两个数相加的和
System.out.println("计算的和为:"+sum);
String str=sum+" ";
char[]str2=str.toCharArray();
//head3=new Node(str2[0]);
for(int i=0;i<str2.length;i++)
{
System.out.println(str2[i]);
}
//记录新链表的头结点
Stack<Integer>stack=new Stack<Integer>();
while(sum!= 0){
int n = sum% 10;
//System.out.println(n);
stack.push(n);
sum /= 10;
}
Node head3=new Node(stack.pop());
//重新生成一个链表，保存两个数相加的和
Node res=head3;
while(!stack.isEmpty())
{
head3.next=new Node(stack.pop());
head3=head3.next;
}
return res;
}
//(利用双栈求解)两个单链表相加生成的链表
public static Node pluslist2(Node head1,Node head2)
{
if(head1==null)
{
return head2;
}else if(head2==null){
return head1;
}else if(head1==null&&head2==null)
{
return null;
}
Stack<Integer> s1 = new Stack<Integer>(); //保存链表1
Stack<Integer> s2 = new Stack<Integer>(); //保存链表2
while (head1 != null) {
s1.push(head1.value);
head1 = head1.next;
}
while (head2 != null) {
s2.push(head2.value);
head2 = head2.next;
}
int ca = 0;
//记录进位
int n1 = 0;
int n2 = 0;
int n = 0;
Node node = null;
Node pre = null;
while (!s1.isEmpty() || !s2.isEmpty()) {
n1 = s1.isEmpty() ? 0 : s1.pop();
n2 = s2.isEmpty() ? 0 : s2.pop();
n = n1 + n2 + ca;
pre = node;
node = new Node(n % 10);
node.next = pre;
ca = n / 10;
}
if (ca == 1) {
pre = node;
node = new Node(1);
node.next = pre;
}
return node;
}
//(利用链表的逆序求解)两个单链表相加生成的链表
public static Node pluslist3(Node head1,Node head2)
{
if(head1==null)
{
return head2;
}else if(head2==null){
return head1;
}else if(head1==null&&head2==null)
{
return null;
}
head1 = reverseList(head1);
head2 = reverseList(head2);
int ca = 0;
int n1 = 0;
int n2 = 0;
int n = 0;
Node c1 = head1;
Node c2 = head2;
Node node = null;
Node pre = null;
while (c1 != null || c2 != null) {
n1 = c1 != null ? c1.value : 0;
n2 = c2 != null ? c2.value : 0;
n = n1 + n2 + ca;
pre = node;
node = new Node(n % 10);
node.next = pre;
ca = n / 10;
c1 = c1 != null ? c1.next : null;
c2 = c2 != null ? c2.next : null;
}
if (ca == 1) {
pre = node;
node = new Node(1);
node.next = pre;
}
reverseList(head1);
reverseList(head2);
return node;
}
//逆序链表
public 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 void PrintList(Node head)
{
while(head!=null)
{
System.out.print(head.value+" ");
head=head.next;
}
}
public static void main(String[]args)
{
//System.out.println("Hello 2017/11/3");
Node node1=new Node(9);
node1.next=new Node(3);
node1.next.next=new Node(7);
Node node2=new Node(6);
node2.next=new Node(3);
//node2.next.next=new Node(3);
//Node mode=pluslist(node1,node2);
//Node mode=pluslist2(node1,node2);
Node mode=pluslist3(node1,node2);
PrintList(mode);
}
}