网站建设入门pdf,wordpress网站标题,cms视频系统大全,个人网站seo题目
给定两个表示非负整数的单向链表#xff0c;请问如何实现这两个整数的相加并且把它们的和仍然用单向链表表示#xff1f;链表中的每个节点表示整数十进制的一位#xff0c;并且头节点对应整数的最高位数而尾节点对应整数的个位数。例如#xff0c;两个分别表示整数98…题目
给定两个表示非负整数的单向链表请问如何实现这两个整数的相加并且把它们的和仍然用单向链表表示链表中的每个节点表示整数十进制的一位并且头节点对应整数的最高位数而尾节点对应整数的个位数。例如两个分别表示整数984和18的链表它们相加时应该是984中的十位数8和18中的十位数1相加984的个位数4和18的个位数8相加。此时不能从两个链表的头节点开始相加而是应该把它们的尾节点对齐并把对应的数位相加。
分析
解决这个问题的办法是把表示整数的链表反转。反转之后的链表的头节点表示个位数尾节点表示最高位数。此时从两个链表的头节点开始相加就相当于从整数的个位数开始相加。在做加法时还需要注意的是进位。如果两个整数的个位数相加的和超过10就会往十位数产生一个进位。在下一步做十位数相加时就要把这个进位考虑进去。
解
public class Test {public static void main(String[] args) {ListNode listNode1 new ListNode(1);ListNode listNode2 new ListNode(2);ListNode listNode3 new ListNode(3);ListNode listNode4 new ListNode(4);ListNode listNode5 new ListNode(5);ListNode listNode6 new ListNode(6);ListNode listNode7 new ListNode(7);ListNode listNode8 new ListNode(8);ListNode listNode9 new ListNode(9);listNode9.next listNode8;listNode8.next listNode4;ListNode result reverseList(listNode1);while (result ! null) {System.out.println(result.val);result result.next;}}public static ListNode addTwoNumbers(ListNode head1, ListNode head2) {head1 reverseList(head1);head2 reverseList(head2);ListNode reversedHead addReversed(head1, head2);return reverseList(reversedHead);}private static ListNode addReversed(ListNode head1, ListNode head2) {ListNode dummy new ListNode(0);ListNode sumNode dummy;int carry 0;while (head1 ! null || head2 ! null) {int sum (head1 null ? 0 : head1.val) (head2 null ? 0 : head2.val) carry;carry sum 10 ? 1 : 0;sum sum 10 ? sum - 10 : sum;ListNode newNode new ListNode(sum);sumNode.next newNode;sumNode sumNode.next;head1 head1 null ? null : head1.next;head2 head2 null ? null : head2.next;}if (carry 0) {sumNode.next new ListNode(carry);}return dummy.next;}public static ListNode reverseList(ListNode head) {ListNode prev null;ListNode cur head;while (cur ! null) {ListNode next cur.next;cur.next prev;prev cur;cur next;}return prev;}
}
