合并两个排序的链表
描述（题目简单） 考点：链表
输入两个递增的链表，单个链表的长度为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,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：
解题思路：
初始化：定义cur指向新链表的头结点
操作：
- 如果L1指向的结点值小于等于L2指向的结点值，则将L1指向的结点值链接到cur的next指针，然后L1指向下一个结点值
- 否则，让L2指向下一个结点值
- 循环步骤1,2，直到L1或者L2为nullptr
- 将L1或者L2剩下的部分链接到cur的后面
题解：
//语言①：C struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) { struct ListNode* vhead = (struct ListNode*)malloc(sizeof( struct ListNode)); //新建一个头结点 vhead->val = -1; struct ListNode* p = vhead; //用一个指针指向该头结点 while (pHead1 && pHead2) { //两个链表都未比较完 if (pHead1->val <= pHead2->val) { //表1的值更小 p->next = pHead1; //先将结点连接到新表，再让原表指针后移一位，二者顺序不可换 pHead1 = pHead1->next; } else { p->next = pHead2; pHead2 = pHead2->next; } p = p->next; //加入一个新结点后，新表指针也后移一位 } p->next = pHead1 ? pHead1 : pHead2; //都比较完后，哪个表非空则直接加入到新表中 return vhead->next; //返回第一个结点 }
function ListNode(x){ this.val = x; this.next = null; } function Merge(pHead1, pHead2) { // write code here if (!pHead1 ) return pHead2; if (!pHead2 ) return pHead1; if(pHead1.val <= pHead2.val){ pHead1.next = Merge(pHead1.next, pHead2); return pHead1 }else{ pHead2.next = Merge(pHead2.next, pHead1); return pHead2 } } module.exports = { Merge : Merge };
