一、题目

力扣原题：https://leetcode-cn.com/problems/sum-lists-lcci/submissions/

二、双指针模拟

/**
* Definition for singly-linked list.
* public class ListNode {
*
int val;
*
ListNode next;
*
ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 保存结果
ListNode result = new ListNode(-1);
ListNode curNode = result;
int carrier = 0;
while (null != l1 && null != l2) {
// 计算当前位
int val = l1.val + l2.val + carrier;
curNode.next = new ListNode(val % 10);
curNode = curNode.next;
// 计算进位
carrier = val / 10;
// 指针后移
l1 = l1.next;
l2 = l2.next;
}
while (null != l1) {
// 计算当前位
int val = l1.val + carrier;
curNode.next = new ListNode(val % 10);
curNode = curNode.next;
// 计算进位
carrier = val / 10;
// 指针后移
l1 = l1.next;
}
while (null != l2) {
// 计算当前位
int val = l2.val + carrier;
curNode.next = new ListNode(val % 10);
curNode = curNode.next;
// 计算进位
carrier = val / 10;
// 指针后移
l2 = l2.next;
}
// 处理最后的进位
if (carrier > 0) {
curNode.next = new ListNode(carrier);
}
return result.next;
}
}

• 基本思路：根据题中的反序链表，可以发现将两个链表的节点依次相加，即是加法竖式的运算，因此通过双指针模拟即可。
• 时间复杂度：O(n1 + n2)。n1为链表1的长度，n2为链表2的长度。
• 空间复杂度：O(max(n1, n2))。n1为链表1的长度，n2为链表2的长度。

三、总结

• 此题还有一个变种，即链表是正序的，这种情况下可以先遍历一次并将元素保存进栈；
• 本题需要注意处理两个链表不等长的情况，以及相加到最后的进位处理；

最后

以上就是失眠酸奶为你收集整理的【链表】链表求和一、题目二、双指针模拟三、总结的全部内容，希望文章能够帮你解决【链表】链表求和一、题目二、双指针模拟三、总结所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。