剑指offer_面试题17_合并两个排序的链表（两种思维）

短命女 2022-08-03 14:58 112阅读 0赞

**题目：输入两个递增排序的链表，合并这两个链表，并使新链表中的结点仍然是按照递增排序的。**

**第一种思维：合并两个排序的链表，类似于合并两个排序数组，所不同的仅是一个用链表保存数据，一个用数组保存数据。**

**算法如下：（下面的算法前提是：头结点 不是 链表的第一个数据节点。）**

/**方法一：合并两个排序链表，使用了新创建的链表来保存，没有改动两个原始链表*/
    ListNode *merge_tow_list(ListNode *pHead1,ListNode *pHead2)
    {
        if(NULL == pHead1 && NULL == pHead2)
            return pHead1;
        if(NULL == pHead1 && NULL != pHead2)
            return pHead2;
        if(NULL != pHead1 && NULL == pHead2)
            return pHead1;
    
        ListNode *temp1, *temp2;
        temp1 = pHead1->m_pNext;        /*指向第一个数据结点*/
        temp2 = pHead2->m_pNext;
    
        ListNode *pHead_new = new ListNode;    /*新建了一个链表用来存放合并后的结点*/
        pHead_new->m_nValue = 0;
        pHead_new->m_pNext = NULL;
    
        ListNode *curr, *temp;
        curr = pHead_new;
    
        while(temp1 != NULL && temp2 != NULL)
        {
            if(temp1->m_nValue < temp2->m_nValue)
            {
                temp = new ListNode;
                temp->m_nValue = temp1->m_nValue;  /*将数据赋值个新节点*/
                temp->m_pNext = NULL;              /*新链表增加的结点，接在链表尾*/
                curr->m_pNext = temp;
    
                pHead_new->m_nValue++;
    
                curr = curr->m_pNext;
                temp1 = temp1->m_pNext;
            }
            else
            {
                temp = new ListNode;
                temp->m_nValue = temp2->m_nValue;
                temp->m_pNext = NULL;
                curr->m_pNext = temp;
    
                pHead_new->m_nValue++;
    
                curr = curr->m_pNext;
                temp2 = temp2->m_pNext;
            }
        }
        while(NULL != temp1)
        {
            temp = new ListNode;
            temp->m_nValue = temp1->m_nValue;
            temp->m_pNext = NULL;
            curr->m_pNext = temp;
    
            pHead_new->m_nValue++;              /*头结点数据保存结点总数，每增加一个数据结点，该值加1*/
    
            curr = curr->m_pNext;
            temp1 = temp1->m_pNext;
        }
        while(NULL != temp2)
        {
            temp = new ListNode;
            temp->m_nValue = temp2->m_nValue;
            temp->m_pNext = NULL;
            curr->m_pNext = temp;
    
            pHead_new->m_nValue++;
    
            curr = curr->m_pNext;
            temp2 = temp2->m_pNext;
        }
    
        return pHead_new;
    }

**以下是合并两个排序数组的算法，可以对比如上算法来看：**

void Merge_array(int a[], n, int b[], m, int c[])
    {
        int i, j, k;
    
        i = j = k = 0;
        while (i < n && j < m)
        {
            if (a[i] < b[j])
                c[k++] = a[i++]; //c[k] = a[i];k++;i++;这里j不变
            else
                c[k++] = b[j++]; //c[k] = b[i];k++;j++;这里i不变
        }
        //到这里总会有一个数组会先结束，将剩下的数组的剩余数据依次补充进c[]就可以了
        while (i < n)
            c[k++] = a[i++];
    
        while (j < m)
            c[k++] = b[j++];
    }

**第二种思维：来源于书本，使用了递归：**

1、从两个链表中找第一个节点，即比较两个链表头结点的数据值，假如链表 1 的第一个结点数据值小，那就把它作为新链表的头街点；

2、找第二个节点时，也是两个链表的头结点比较，此时链表 1 的头结点为上一步被取走结点的下一结点，链表 2 的头结点则还是原来链表的头结点。比较这两个 头结点，谁小 则取出并接在 新链表头结点后。

3、其他结点，依次类推。。。

其中第 2 步，我们可以发现，这里可以很方便的用 **递归** 的原理来解决。

以这种方法解决问题，需要有这样的前提：链表的第一个数据结点，即为头结点。（这与第一种思维的前提不同）

**算法如下**

/**第二种方法：使用递归,适合头结点就是第一个数据结点的链表表示方法*/
    /**代码非常简洁，巧妙*/
    ListNode * merge_tow_list2(ListNode *pHead1,ListNode *pHead2)
    {
        if(NULL == pHead1)
            return pHead2;
        else if(NULL == pHead2)
            return pHead1;
    
        ListNode *pMergedHead = NULL;
    
        if(pHead1->m_nValue < pHead1->m_nValue)
        {
            pMergedHead = pHead1;
            pMergedHead->m_pNext = merge_tow_list2(pHead1->m_pNext,pHead2);
        }
        else
        {
            pMergedHead = pHead2;
            pMergedHead->m_pNext = merge_tow_list2(pHead1,pHead2->m_pNext);
        }
    
        return pMergedHead;
    }

**主函数如下：**（这里只测试了，第一种方法的代码）

int main()
    {
        int n_of_list1 = 6;
        int n_of_list2 = 3;
        int i = 1,j = 2;
        ListNode *pHead1,*pHead2,*pHead;
        pHead1 = creat_List();
        while(n_of_list1 > 0)
        {
            insert_Node_behind(pHead1,i);
            i += 2;
            n_of_list1--;
        }
        pHead2 = creat_List();
        while(n_of_list2 > 0)
        {
            insert_Node_behind(pHead2,j);
            j += 2;
            n_of_list2--;
        }
        show_List(pHead1);
        show_List(pHead2);
    
        pHead = merge_tow_list(pHead1,pHead2);
        show_List(pHead);
    
        return 0;
    }

**结果如下：**（其他测试用例，可以改变主函数中的数据得到）

![20150810221033073][]

/\*点滴积累，我的一小步O(∩\_∩)O~\*/

[20150810221033073]: /images/20220731/b189a00c60164672b7d443d2dc57d7cf.png