博客学算法———合并有序链表

首先我们来看一下我们的题目，今日份的题目比较简单，这道题目就是链表的简单操作，说难很简单，说简单，但是它却并不是那么容易。

将两个链表链接并不是那么难。第一种方法：

/**
 \* Definition for singly-linked list.
 \* struct ListNode {
 \*     int val;
 \*     struct ListNode *next;
 \* };
 */
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {

   struct ListNode *p1 = l1, *p2 = l2;
   struct ListNode  *head = NULL, *p = NULL; //定义新链表的头结点和尾结点
/* 确定新链表头 */
if(p1 != NULL && p2 != NULL){
    if(p1->val < p2->val){
        head = p1;
        p1 = p1->next;
    }else{
        head = p2;
        p2 = p2->next;
    }
}else if(p1 != NULL){
    return p1;
}else{
    return p2;
}

/* 拼接小值结点*/
p = head; //这样可以用尾插法
while(p1 != NULL && p2 != NULL){
    if(p1->val < p2->val){
        p = p->next = p1;
        p1 = p1->next;
    }else{
        p = p->next = p2;
        p2 = p2->next;
    }
}
if(p1 != NULL){  //如果p1不空，将p1剩余部分拼接到新链表之后
    p->next = p1;
}else if(p2 != NULL){  //如果p2不空，将p2剩余部分拼接到新链表之后
    p->next = p2;  
}
return head;
}

这种方法主要难点是在比较过程中不断寻找头结点，最后使用尾插法，插入新的链表之中，然后将新的链表返回即可。
第二种方法：递归法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode* head;
    if(!l1)
        return l2;
    if(!l2)
        return l1;
    if(l1->val < l2->val)
    {
        head = l1;
        head->next = mergeTwoLists(l1->next,l2);
    }
    else
    {
        head = l2;
        head->next = mergeTwoLists(l1,l2->next);
    }
    return head;
}