文章目录
- 一、题目
- 二、C# 题解
一、题目
给定两个用链表表示的整数,每个节点包含一个数位。
这些数位是反向存放的,也就是个位排在链表首部。
编写函数对这两个整数求和,并用链表形式返回结果。
点击此处跳转题目。
示例:
输入:(7 -> 1 -> 6) + (5 -> 9 -> 2),即617 + 295
输出:2 -> 1 -> 9,即912
进阶:思考一下,假设这些数位是正向存放的,又该如何解决呢?
示例:
输入:(6 -> 1 -> 7) + (2 -> 9 -> 5),即617 + 295
输出:9 -> 1 -> 2,即912
二、C# 题解
很基础的题目了,这里遍历两个链表,均为 null 才停止:
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
ListNode p = new ListNode(0), q = p;
int a, b, sum, n = 0;
while (l1 != null || l2 != null || n != 0) {
a = l1 == null ? 0 : l1.val;
b = l2 == null ? 0 : l2.val;
sum = a + b + n;
q.val = sum % 10;
n = sum / 10;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
if (l1 != null || l2 != null || n != 0) {
q.next = new ListNode(0);
q = q.next;
}
}
return p;
}
}
- 时间复杂度: O ( M a x ( m , n ) ) O(Max(m,n)) O(Max(m,n))。
- 空间复杂度: O ( M a x ( m , n ) ) O(Max(m,n)) O(Max(m,n))。