题解 | #链表相加(二)#
链表相加(二)
https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b
今日做的较难的一道算法题，贴上解题思路和代码以供后续学习参考
首先，运用反转链表将两个链表反转，可以顺位得到个十百千位，再创建虚拟头结点，以及进位计数器carry
public ListNode addInList(ListNode head1, ListNode head2) {
ListNode h1 = ReverseList(head1);
ListNode h2 = ReverseList(head2);
int carry = 0;
ListNode head3 = new ListNode(-1);
ListNode h3 = head3;
其次，运用while循环依次将h1和h2的val值相加并传入tmp中，再创建新的链表节点去接收tmp%10作为它的值
public ListNode addInList(ListNode head1, ListNode head2) {
ListNode h1 = ReverseList(head1);
ListNode h2 = ReverseList(head2);
int carry = 0;
ListNode head3 = new ListNode(-1);
ListNode h3 = head3;
while (h1 != null || h2 != null) {
int tmp = carry;
if (h1 != null) {
tmp+=h1.val;
h1=h1.next;
}
if (h2 != null) {
tmp+=h2.val;
h2=h2.next;
}
carry=tmp/10;//如果有进位，1会被传上去
h3.next=new ListNode(tmp%10);//创建新的链表节点
h3=h3.next;
}
最后，如果carry进位，需要再创建一个节点用来接收carry值
if (carry!=0) {
h3.next = new ListNode(carry);
}
return ReverseList(head3.next);// 不要忘了最后把新链表再反转回去！！！
}
这里是反转链表的代码public ListNode ReverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode CurNext = cur.next;
cur.next = pre;
pre = cur;
cur = CurNext;
}
return pre;
}
以上
投递腾讯等公司10个岗位 >
拼多多集团-PDD公司氛围 518人发布