leetcode 21. Merge Two Sorted Lists 合并两条链表

递归合并： 

#include<iostream>
#include <stdio.h>
#include <stdlib.h>using namespace std;struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};ListNode* CreateListNode(int value); //创建一个节点
void PrintList(ListNode* head); //打印整个链表
void PrintListNode(ListNode* node); //打印节点的值
void ConnectListNodes(ListNode* cur, ListNode* Next); //将两个结点连接起来
void DestroyList(ListNode* head); //销毁链表class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if (l1 == nullptr) return l2;if (l2 == nullptr) return l1;ListNode *l3;if (l1->val < l2->val){l3 = l1;l3->next = mergeTwoLists(l1->next, l2);}else{l3 = l2;l3->next = mergeTwoLists(l1, l2->next);}return l3;}
};int main()
{ListNode* node1 = CreateListNode(1); //建立节点ListNode* node2 = CreateListNode(3);ListNode* node3 = CreateListNode(5);ListNode* node4 = CreateListNode(7);ListNode* node5 = CreateListNode(9);ConnectListNodes(node1, node2); //连接结点ConnectListNodes(node2, node3);ConnectListNodes(node3, node4);ConnectListNodes(node4, node5);printf("the first list: \n");PrintList(node1); //打印以node1为头节点的链表ListNode* node11 = CreateListNode(2);ListNode* node12 = CreateListNode(4);ListNode* node13 = CreateListNode(6);ListNode* node14 = CreateListNode(8);ConnectListNodes(node11, node12);ConnectListNodes(node12, node13);ConnectListNodes(node13, node14);printf("\nthe second list: \n");PrintList(node11);printf("after merging:\n");Solution solution;ListNode* resultHead = solution.mergeTwoLists(node1, node11);PrintList(resultHead);DestroyList(resultHead);system("pause");return 0;
}/*----创建一个节点----*/
ListNode* CreateListNode(int value) 
{//ListNode* node = new ListNode();ListNode* node;node->val = value;node->next = NULL;return node;
}
/*----打印整个链表----*/
void PrintList(ListNode* head) 
{printf("PrintList starts.\n");ListNode* node = head;while (node != NULL){printf("%d\t", node->val);node = node->next;}
}
/*----打印一个结点的值----*/
void PrintListNode(ListNode* node)
{if (node == NULL) printf("The node is NULL\n");elseprintf("The key in node is %d.\n", node->val);
}/*---将两个结点连接起来---*/
void ConnectListNodes(ListNode* cur, ListNode* Next)
{if (cur == NULL){printf("Error to connect two nodes.\n");exit(1);}cur->next = Next;
}
/*---销毁链表-----*/
void DestroyList(ListNode* head)
{ListNode* node = head;while (node != NULL){head = head->next;delete node;node = head;}
}

非递归合并：

ListNode* Merge(ListNode* l1, ListNode* l2)
{if (l1 == NULL || l2 == NULL)return l1 == NULL ? l2 : l1;ListNode*head = NULL;ListNode *p1 = l1;ListNode *p2 = l2;ListNode *p = head;while (p1 != NULL&&p2 != NULL){ListNode *q = NULL;if (p1->val <= p2->val)q = p1;else q = p2;//  =p1->val<=p2->val?p1:p2;if (head == NULL)//初次插入结点{p = q;(q == p1) ? (p1 = p1->next) : (p2 = p2->next);p->next = NULL;head = p;//这里很重要啊！！！}else{p->next = q;(q == p1) ? (p1 = p1->next) : (p2 = p2->next);p = p->next;p->next = NULL;}}p->next = (p1 == NULL) ? p2 : p1;return head;
}