高端品牌网站建设优势_哈尔滨公司网页制作_网站备案_百度指数在线查询小程序

解题思路：

1. 处理特殊情况： 若其中一个链表为空，直接返回另一个链表。
2. 创建虚拟头节点： 简化链表操作，避免处理头节点的特殊情况。
3. ​遍历合并： 使用双指针遍历两个链表，每次选择较小的节点连接到结果链表，并移动对应链表的指针。
4. 处理剩余节点： 当一个链表遍历完毕后，将另一个链表的剩余部分直接连接到结果链表尾部。

Java代码：

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if (list1 == null) return list2;if (list2 == null) return list1;ListNode dummyHead = new ListNode(-1);ListNode current = dummyHead;while (list1 != null && list2 != null) {if (list1.val <= list2.val) {current.next = list1;list1 = list1.next;} else {current.next = list2;list2 = list2.next;}current = current.next;}current.next = (list1 == null) ? list2 : list1;return dummyHead.next;}
}

复杂度分析：

• 时间复杂度： O(n + m)，其中 n 和 m 分别是两个链表的长度。需要遍历两个链表的所有节点一次。
• 空间复杂度： O(1)。仅使用了常数额外空间（虚拟头节点和指针变量），没有额外开辟存储空间。

解题思路：

1. 初始化变量： 创建一个虚拟头节点 dummyHead 和一个指针 current 指向它，用于构建结果链表。初始化进位 carry 为 0。
2. 遍历链表： 使用循环遍历两个链表，直到两个链表都处理完且进位为 0。
3. 处理剩余进位： 如果循环结束后仍有进位，需将其添加到结果链表中。

Java代码：

class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode dummyHead = new ListNode(-1);ListNode current = dummyHead;int carry = 0;while (l1 != null || l2 != null || carry != 0) {int val1 = (l1 != null) ? l1.val : 0;int val2 = (l2 != null) ? l2.val : 0;int sum = val1 + val2 + carry;carry = sum / 10;current.next = new ListNode(sum % 10);current = current.next;if (l1 != null) l1 = l1.next;if (l2 != null) l2 = l2.next;}return dummyHead.next;}
}

复杂度分析：

• 时间复杂度： O(n + m)，其中 n 和 m 分别是两个链表的长度。每个节点最多被访问一次。
• 空间复杂度： O(1)。仅使用了常数额外空间（虚拟头节点和指针变量），结果链表的空间由输入决定，不计入额外空间复杂度。