算法总结之 两个单链表生成相加的链表 |
您所在的位置:网站首页 › 两个单链表相加 › 算法总结之 两个单链表生成相加的链表 |
对于这个问题还有一个很好的方法: 1、将两个链表逆序,这样就可以依次得到从低到高位的数字 2、同步遍历两个逆序后链表,相加生成新链表,同时关注进位 3、当两个链表都遍历完成后,关注进位。 4、 将两个逆序的链表再逆序一遍,调整回去 返回结果链表 package TT; public class Test98 { public class Node{ public int value; public Node next; public Node(int data){ this.value=data; } } public Node addLists2(Node head1, Node head2){ 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; } }
|
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |