每日一题 为了工作 2020 0325 第二十五题
/**
*
* 问题：两个单链表相加生成相加链表
* 假设链表中每一个节点的值都在0-9之间， 那么链表整体就可以代表一个整数。
* 例如： 9->3->7, 可以代表整数 937。
* 给定两个这种链表的头节点 head1和 head2, 请生成代表两个整数相加值的结果链表。
* 例如： 链表 1为 9->3->7, 链表 2为 6->3, 最后生成新的结果链表为 1->0->0->0。
*
* 解答：
* 利用链表的逆序求解。
* 1.将两个链表逆序， 这样就可以依次得到从低位到高位的数字。
* 例如： 链表9->3->7, 逆序后变为7->3->9; 链表6->3, 逆序后变为3->6。
*
* 2.同步遍历两个逆序后的链表， 这样就依次得到两个链表从低位到高位的数字， 在
* 这个过程中生成相加链表即可， 同时需要关注每一步是否有进位， 用ca表示。
*
* 3.当两个链表都遍历完成后， 还要关注进位信息是否为1, 如果为1, 还要生成一
* 个节点值为1的新节点。
*
* 4.将两个逆序的链表再逆序一次， 即调整成原来的样子。
*
* 5. 返回新生成的结果链表。。
*
* @author 雪瞳
*
*/
*代码
public class Node {
public int value;
public Node next;
public Node (int data){
this.value=data;
}
}
public class AddList {
//逆序单链表
public Node reverseList(Node head){
Node current = null;
Node currentNext =null;
current = head.next;
head.next=null;
while(current!=null){
currentNext=current.next;
current.next=head;
head=current;
current=currentNext;
}
return head;
}
public Node addList(Node head1,Node head2){
int ca=0;
int sum=0;
int value1=0;
int value2=0;
Node newNode=null;
Node current = null;
Node last = null;
AddList al = new AddList();
head1=al.reverseList(head1);
head2=al.reverseList(head2);
while(head1!=null || head2!=null){
value1=head1!=null?head1.value:0;
value2=head2!=null?head2.value:0;
sum=value1+value2+ca;
if(sum>=10){
sum -= 10;
ca = 1;
}
newNode = new Node(sum);
if(current==null){
current=newNode;
}else{
last=current;
while(last.next!=null){
last=last.next;
}
last.next=newNode;
}
head1=head1.next;
head2=head2.next;
}
if(ca==1){
newNode=new Node(1);
last=current;
while(last.next!=null){
last=last.next;
}
last.next=newNode;
}
current=al.reverseList(current);
return current;
}
}
import java.util.Random;
import java.util.Scanner;
public class TestAddList {
public static void main(String[] args) {
TestAddList test = new TestAddList();
AddList add = new AddList();
Scanner sc = new Scanner(System.in);
int length1;
System.out.println("请输入链表长度：...");
length1 = sc.nextInt();
int length2;
System.out.println("请输入链表长度：...");
length2 = sc.nextInt();
Node head1;
Node head2;
head1=test.getNodeList(length1);
head2=test.getNodeList(length2);
System.out.println("初始状态...");
test.showByTip(head1);
test.showByTip(head2);
Node addHead = add.addList(head1, head2);
System.out.println("求和后状态...");
test.showByTip(addHead);
}
public void showByTip(Node head) {
Node current = null;
System.out.println("链表内的元素顺序显示如下：...");
current=head;
while(current!=null) {
System.out.print(current.value+" ");
current=current.next;
}
System.out.println("");
}
public Node getNodeList(int listLength) {
Random rand = new Random();
Node nodeList[]= new Node[listLength];
for(int i=0;i<listLength;i++) {
nodeList[i]= new Node(rand.nextInt(10));
}
for(int i=0;i<listLength-1;i++) {
nodeList[i].next=nodeList[i+1];
}
return nodeList[0];
}
}
*运行结果