合并两个升序的单向链表

合并两个升序的单向链表

题目描述：合并两个升序的单向链表
分析：合并排序的单向链表和合并排序好的数组是类似的；
1：分配一个新的节点，让newHead指针和tail指针指向新分配的节点；
2：从两个链表头部开始，逐个比较2个链表的节点值让tail指向节点的next域指向head1或head2,
3: 移动tail指针
4：移动 head1 或 head2 到下一个节点

代码如下：

ListNode* MergeTwoSortedList(ListNode *head1, ListNode *head2){  
    if (head1 == NULL) {
    	return head2;  
    } 
        
    if (head2 == NULL) {
    	return head1;  
    } 
trueListNode* p1 = head1, p2 = head2;
true//分配一个新的节点
trueListNode* newHead = (ListNode*)(malloc(size(ListNode)));
trueListNode* tail = newHead;

truewhile(p1 != NULL && p2 != NULL){
truetrueif (p1 -> val <= p2 -> val){
truetruetruetail -> next = p1;
truetruetruetail = p1;
truetruetruep1 = p1 -> next;
truetrue}else {
truetruetruetail -> next = p2;
truetruetruetail = p2;
truetruetruep2 = p2 -> next;	
truetrue}	
true}
trueif (p1){
true 	tail -> next = p1;
true} 
trueif(p2){
truetruetail -> next = p2;
true}

truereturn newHead -> next;
}