21. 合并两个有序链表（单链表

方法一：递归

• 递归边界为一条链空时，直接当前及以后结点直接返回另一条链即可
• 否则不断取两个链首元素中权值小的做当前结点，并从未连接的结点中递归下一个结点

  class Solution {
  public:
      ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
          if(list1==NULL)return list2;//链1为空，接上链2
  		else if(list2==NULL)return list1;//链2为空，接上链1
  		else if(list1->val<list2->val){//取两个链首元素中权值小的做当前结点，并从未连接的结点中递归下一个结点
  			list1->next=mergeTwoLists(list1->next,list2);
  			return list1; 
  		}else{
  			list2->next=mergeTwoLists(list1,list2->next);
  			return list2;
  		} 
      }
  };
  

方法二：迭代

• 利用两个链首指针，在都未遍历到链尾情况下比较两指针指向结点权值，将权值小的结点放在结果链后，并让对应链、结果链指针后移
• 最后两个链表谁还有剩余，则再接上谁即可

  class Solution {
  public:
      ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
          ListNode *list=new ListNode(0),*p=list;//新建伪头结点 
  		while(list1!=NULL&&list2!=NULL){//在两个链表的公共部分，谁结点权值小连上谁，并让对应链、结果链指针后移 
  			if(list1->val<list2->val){
  				p->next=list1;
  				list1=list1->next;
  			}else{
  				p->next=list2;
  				list2=list2->next;
  			}
  			p=p->next;
  		}
  		if(list1)p->next=list1;//两个链表谁有剩余，则再接上谁 
  		else p->next=list2;
  		return list->next; 
      }
  };