JZ16 合并两个排序的链表

本文最后更新于：2022年4月9日 中午

image-20211006110116949

Solution

  • 递归法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
// 递归法
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        if (pHead1 == nullptr) return pHead2;
        else if (pHead2 == nullptr) return pHead1;
        else if (pHead1->val < pHead2->val) {
            pHead1->next = Merge(pHead1->next, pHead2);
            return pHead1;
        } else {
            pHead2->next = Merge(pHead1, pHead2->next);
            return pHead2;
        }
    }
};
  • 迭代法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode* dummyHead = new ListNode(-1);
        ListNode* cur = dummyHead;
        while (pHead1 && pHead2) {
            if (pHead1->val < pHead2->val) {
                cur->next = pHead1;
                pHead1 = pHead1->next;
                cur = cur->next;
            } else {
                cur->next = pHead2;
                pHead2 = pHead2->next;
                cur = cur->next;
            }
        }
        cur->next = pHead1 ? pHead1 : pHead2;
        return dummyHead->next;
    }
};
algo 链表 nowcoder

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！