合并两个排序的链表

标签：pre ListNode val 合并 next 链表 pHead1 排序

• 描述

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
  数据范围： 0≤n≤1000，−1000≤节点值≤1000
要求：空间复杂度 O(1)，时间复杂度 O(n)
  如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}  

• 示例1

输入：{1,3,5},{2,4,6} 返回值：{1,2,3,4,5,6}  

• 示例2

输入：{},{} 返回值：{}  

• 算法思想

先进行特殊情况的判断，若有一个链表为空，则返回另一个链表。 然后再判断哪个链表的头结点的值小，将头结点值大的链表合并至头结点值小的链表当中。 最后，若头结点值小的链表已到尾部，而头结点值大的链表仍有元素，就将剩下元素直接放到目标链表的尾部，并返回相应的目标链表。  

• 代码

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6             val(x), next(NULL) {
 7     }
 8 };*/
 9 class Solution {
10   public:
11     ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
12         ListNode* pre = nullptr;
13         ListNode* p = pHead1;
14         ListNode* q = pHead2;
15         //特殊情况判断
16         if(pHead1==nullptr)  return pHead2;
17         if(pHead2==nullptr)  return pHead1;
18         //L2合并至L1
19         if (q->val >= p->val) {
20             while (p && q) {
21                 if (q->val >= p->val) {
22                     pre = p;
23                     p = pre->next;
24                 } else {
25                     ListNode* r = q->next;
26                     q->next = p;
27                     pre->next = q;
28                     pre = q;
29                     q = r;
30                 }
31             }
32 
33             if (q) {
34                 pre->next = q;
35             }
36             return pHead1;
37         } else {          //L1合并至L2
38             while (p && q) {
39                 if (p->val >= q->val) {
40                     pre = q;
41                     q = pre->next;
42                 } else {
43                     ListNode* r = p->next;
44                     p->next = q;
45                     pre->next = p;
46                     pre = p;
47                     p = r;
48                 }
49             }
50             if (p) {
51                 pre->next = p;
52             }
53             return pHead2;
54         }
55     }
56 };

 

标签：pre,ListNode,val,合并,next,链表,pHead1,排序
From： https://www.cnblogs.com/yueshengd/p/17373877.html