实现两个大数相加 包括字符串和 链表实现。
public static void main(String[] args) {
ListNode header = new ListNode(1);
header.next = new ListNode(2);
header.next.next = new ListNode(3);
header.next.next.next = new ListNode(4);
header.next.next.next.next = new ListNode(5);
ListNode header1 = new ListNode(1);
header1.next = new ListNode(2);
header1.next.next = new ListNode(3);
ListNode result = add(header,header1);
while(result != null){
System.out.print(result.value);
result = result.next;
}
}
//链表反转
private static ListNode reverseList(ListNode head) { //1
ListNode prev = null; // 2
ListNode curr = head; // 3
while (curr != null) { //4
ListNode nextTemp = curr.next; //5
curr.next = prev; // 6
prev = curr; //7
curr = nextTemp; //8
}
return prev; //9
}
//这是错误写法！！！
private static ListNode reverseListNode(ListNode header){
if(header == null || header.next == null){
return header;
}
printNodeList(header);
ListNode preNode = header;
ListNode curNode = header.next;
while (curNode.next != null){
ListNode temp = curNode.next;
preNode.next = null;
curNode.next = preNode;
preNode = curNode;
curNode = temp;
}
curNode.next = preNode;
printNodeList(curNode);
return curNode;
}
static void printNodeList(ListNode head){
System.out.println("======start========");
while(head != null){
System.out.println(head.value);
head = head.next;
}
System.out.println("======end========");
}
//链表
private static ListNode add(ListNode header1,ListNode header2){
if(header1 == null || header2 == null){
return null;
}
header1 = reverseListNode(header1);
header2 = reverseListNode(header2);
ListNode result = null;
ListNode curNode = null;
int lastNum = 0;
while(header1 != null || header2 != null){
int num1 = header1 != null ? header1.value : 0;
int num2 = header2 != null ? header2.value : 0;
int sum = num1 + num2;
int curNum = sum > 10 ? (sum % 10) : sum;
curNum += lastNum;
lastNum = sum >= 10 ? 1 : 0;
if(result == null){
result = new ListNode();
result.value = curNum;
curNode = result;
}else{
curNode.next = new ListNode();
curNode.next.value = curNum;
curNode = curNode.next;
}
if(header1 != null){
header1 = header1.next;
}
if(header2 != null){
header2 = header2.next;
}
}
if(lastNum > 0){
curNode.next = new ListNode();
curNode.next.value = lastNum;
}
return reverseListNode(result);
}
//字符串
private static void addStr(String numStr1,String numStr2){
if(numStr1 == null || numStr1 == null){
return;
}
int l1 = numStr1.length();
int l2 = numStr2.length();
int maxLength = l1 > l2 ? l1 : l2;
StringBuilder sbSum = new StringBuilder();
int lastNum = 0;
for(int i = 0;i < maxLength;i++){
int num1 = l1 > i ? numStr1.charAt(l1 - 1 - i) - '0' : 0;
int num2 = l2 > i ? numStr2.charAt(l2 - 1 - i) - '0' : 0;
int sum = num1 + num2;
int curNum = sum > 10 ? (sum % 10) : sum;
curNum += lastNum;
lastNum = sum >= 10 ? 1 : 0;
sbSum.append(String.valueOf(curNum));
}
if(lastNum > 0){
sbSum.append(lastNum);
}
System.out.println(sbSum.reverse().toString());
}
static class ListNode{
private ListNode next;
private int value;
public ListNode(){
this(-1);
}
public ListNode(int value){
this.value = value;
}
}
