#yyds干货盘点# 面试必刷TOP101：链表相加(二)

#yyds干货盘点# 面试必刷TOP101：链表相加(二)

1.简述：

描述

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。

给定两个这种链表，请生成代表两个整数相加值的结果链表。

例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。

示例1

输入：

[9,3,7],[6,3]

返回值：

{1,0,0,0}

示例2

输入：

[0],[6,3]

返回值：

{6,3}

2.代码实现：

import java.util.*;/* * public class ListNode { * int val; * ListNode next = null; * } */public class Solution { /** * * @param head1 ListNode类 * @param head2 ListNode类 * @return ListNode类 */ public ListNode addInList (ListNode head1, ListNode head2) { // 进行判空处理 if(head1 == null) return head2; if(head2 == null){ return head1; } // 反转h1链表 head1 = reverse(head1); // 反转h2链表 head2 = reverse(head2); // 创建新的链表头节点 ListNode head = new ListNode(-1); ListNode nHead = head; // 记录进位的数值 int tmp = 0; while(head1 != null || head2 != null){ // val用来累加此时的数值（加数+加数+上一位的进位=当前总的数值） int val = tmp; // 当节点不为空的时候，则需要加上当前节点的值 if (head1 != null) { val += head1.val; head1 = head1.next; } // 当节点不为空的时候，则需要加上当前节点的值 if (head2 != null) { val += head2.val; head2 = head2.next; } // 求出进位 tmp = val/10; // 进位后剩下的数值即为当前节点的数值 nHead.next = new ListNode(val%10); // 下一个节点 nHead = nHead.next; } // 最后当两条链表都加完的时候，进位不为0的时候，则需要再加上这个进位 if(tmp > 0){ nHead.next = new ListNode(tmp); } // 重新反转回来返回 return reverse(head.next); } // 反转链表 ListNode reverse(ListNode head){ if(head == null) return head; ListNode cur = head; ListNode node = null; while(cur != null){ ListNode tail = cur.next; cur.next = node; node = cur; cur = tail; } return node; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。