建设工程有限公司企业网站电脑编程培训

Leetcode 21. 合并两个有序链表

题目链接

思路：

• 和归并排序中 merge 部分一致
  1. 两个指针分别指向 2 个链表头
  2. 每次选小的那个加入 res 中，对应指针后移一位;
  3. 重复步骤2，直至一个指针到链表末尾
  4. 将另一个剩余的全部 copy 到 res 中，链表只需要修改末尾结点指向
• 链表添加结点操作

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* res = new ListNode();ListNode* p = res;while (list1 && list2) {int x = list1->val;int y = list2->val;if (x <= y) {p->next = list1;list1 = list1->next;}else {p->next = list2;list2 = list2->next;}p = p->next;}if (list1 && !list2) {p->next = list1;}if (list2 && !list1) {p->next = list2;}return res->next;}
};