剑指Offer - 面试题25：合并俩个排序的链表-阿里云开发者社区

题目

输入俩个递增排序的链表，合并这俩个链表并使新链表中的节点仍然是递增序列。例如下图链表1和链表2，合并后的升序链表为链表3，链表节点定义如下：

typedef int TElemType;//链表节点值的数据类型
struct ListNode
{
    TElemType m_nValue;
    ListNode* m_pNext;
};

分析

我们可以构造出来一个链表。表头不存储数据，定义俩指针p1和p2分别指向链表1和链表2表头。再创建一个记录新的链表尾部的指针previously。然后对比俩指针所指节点的值，谁小取谁的值，然后对应的指针后移。将新的节点连接到previously指向的节点后面，然后更新previously。直到俩个链表有一个为nullptr或者俩个均为nullptr。

当有一个链表为空退出循环时，直接将previously的下一个节点连接到另一个链表指针的节点。若均为nullptr时，不进行任何操作。(但是如果题目要求不允许修改原链表，你就只能继续遍历链表，然后创建新节点，连接。)

下面代码是不允许修改的原链表代码，且未优化

C++

#include <iostream>
using namespace std;
typedef int TElemType;//链表节点值的数据类型
struct ListNode
{
    TElemType m_nValue;
    ListNode* m_pNext;
};
ListNode* CreateNode(TElemType val)//创建节点
{
    ListNode* Node = new ListNode();
    Node->m_nValue = val;
    Node->m_pNext = nullptr;
    return Node;
}
void connect(ListNode* L1, ListNode* L2)//链接
{
    L1->m_pNext = L2;
}
void PrintList(ListNode* head)
{
    while (head != nullptr)
    {
        cout << head->m_nValue;
        if (head->m_pNext != nullptr)
        {
            cout << "->";
        }
        else
        {
            cout << endl;
        }
        head = head->m_pNext;
    }
}
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)//合并俩链表
{
    if (nullptr == pHead1 && nullptr == pHead2)
    {
       return nullptr;
    }
    if (nullptr == pHead1)
    {
        return pHead2;
    }
    if (nullptr == pHead2)
    {
        return pHead1;
    }
    ListNode* p1 = pHead1;
    ListNode* p2 = pHead2;
    ListNode* NewNode = nullptr;//新创建的节点指针
    ListNode* head = new ListNode();//新链表的表头指针
    head->m_nValue = 0;
    head->m_pNext = nullptr;
    ListNode* previously = head;//表尾指针
    while (p1 != nullptr && p2 != nullptr)
    {
        int min = 0;//用于保存小值的节点
        //找最小值
        if (p1->m_nValue < p2->m_nValue)
        {
            min = p1->m_nValue;
            p1 = p1->m_pNext;
        }
        else
        {
            min = p2->m_nValue;
            p2 = p2->m_pNext;
        }
        //创建新节点
        NewNode = new ListNode();
        NewNode->m_nValue = min;
        NewNode->m_pNext = nullptr;
        //连接
        previously->m_pNext = NewNode;
        //更新链表尾指针
        previously = NewNode;
    }
    /*不可修改原链表的代码*/
    while (p1 != nullptr)
    {
        int min = p1->m_nValue;
        p1 = p1->m_pNext;
        //创建新节点
        NewNode = new ListNode();
        NewNode->m_nValue = min;
        NewNode->m_pNext = nullptr;
        //连接
        previously->m_pNext = NewNode;
        //更新链表尾指针
        previously = NewNode;
    }
    /*不可修改原链表的代码*/
    while (p2 != nullptr)
    {
        int min = p2->m_nValue;
        p2 = p2->m_pNext;
        //创建新节点
        NewNode = new ListNode();
        NewNode->m_nValue = min;
        NewNode->m_pNext = nullptr;
        //连接
        previously->m_pNext = NewNode;
        //更新链表尾指针
        previously = NewNode;
    }
    return head->m_pNext;
}
int main()
{
    /*测试用例1*/
    // 1 3 5 7       2 4 6 8
    ListNode* Node1 = CreateNode(1);
    ListNode* Node3 = CreateNode(3);
    ListNode* Node5 = CreateNode(5);
    ListNode* Node7 = CreateNode(7);
    ListNode* Node2 = CreateNode(2); 
    ListNode* Node4 = CreateNode(4); 
    ListNode* Node6 = CreateNode(6);
    ListNode* Node8 = CreateNode(8);
    connect(Node1, Node3);
    connect(Node3, Node5);
    connect(Node5, Node7);
    connect(Node2, Node4);
    connect(Node4, Node6);
    connect(Node6, Node8);
    cout << "链表1:";
    PrintList(Node1);
    cout << "链表2:";
    PrintList(Node2);
    ListNode* head = Merge(Node1, Node2);
    cout << "合并后的链表：";
    PrintList(head);
    cout << "--------------------------------------" << endl;
    /*测试用例2*/
    // 1 2 4      3 5 8  
    Node1 = CreateNode(1);
    Node2 = CreateNode(2);
    Node4 = CreateNode(4);
    Node3 = CreateNode(3);
    Node5 = CreateNode(5);
    Node8 = CreateNode(8);
    connect(Node1, Node2);
    connect(Node2, Node4);
    connect(Node3, Node5);
    connect(Node5, Node8);
    cout << "链表1:";
    PrintList(Node1);
    cout << "链表2:";
    PrintList(Node3);
    head = Merge(Node1, Node3);
    cout << "合并后的链表：";
    PrintList(head);
    return 0;
}

上述代码中发现创建新节点多次重复我们可以封装成一个函数

    int min = p2->m_nValue;
        p2 = p2->m_pNext;
        //创建新节点
        NewNode = new ListNode();
        NewNode->m_nValue = min;
        NewNode->m_pNext = nullptr;
        //连接
        previously->m_pNext = NewNode;
        //更新链表尾指针
        previously = NewNode;

优化后的不允许修改原链表代码

C++

#include <iostream>
using namespace std;
typedef int TElemType;//链表节点值的数据类型
struct ListNode
{
  TElemType m_nValue;
  ListNode* m_pNext;
};
ListNode* CreateNode(TElemType val)//创建节点
{
  ListNode* Node = new ListNode();
  Node->m_nValue = val;
  Node->m_pNext = nullptr;
  return Node;
}
void connect(ListNode* L1, ListNode* L2)//链接
{
  L1->m_pNext = L2;
}
void PrintList(ListNode* head)//输出
{
  while (head != nullptr)
  {
    cout << head->m_nValue;
    if (head->m_pNext != nullptr)
    {
      cout << "->";
    }
    else
    {
      cout << endl;
    }
    head = head->m_pNext;
  }
}
//创建并连接新节点
//此处传参必须要二级指针，因为要修改指针
void connNewNode(ListNode** previously, ListNode** p)
{
  //创建新节点
  ListNode* NewNode = new ListNode();
  NewNode->m_nValue = (*p)->m_nValue;
  NewNode->m_pNext = nullptr;
  //连接
  (*previously)->m_pNext = NewNode;
  //更新新链表尾指针
  *previously = NewNode;
  //更新原链表指针
  *p = (*p)->m_pNext;
}
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)//合并俩链表
{
  if (nullptr == pHead1)
  {
    return pHead2;
  }
  if (nullptr == pHead2)
  {
    return pHead1;
  }
  ListNode* p1 = pHead1;
  ListNode* p2 = pHead2;
  ListNode* head = new ListNode();//新链表的表头指针
  head->m_nValue = 0;
  head->m_pNext = nullptr;
  ListNode* previously = head;//表尾指针
  while (p1 != nullptr && p2 != nullptr)
  {
    if (p1->m_nValue < p2->m_nValue)
    {
      connNewNode(&previously, &p1);
    }
    else
    {
      connNewNode(&previously, &p2);
    }
  }
  /*不可修改原链表的代码*/
  while (p1 != nullptr)
  {
    connNewNode(&previously, &p1);
  }
  /*不可修改原链表的代码*/
  while (p2 != nullptr)
  {
    connNewNode(&previously, &p2);
  }
  return head->m_pNext;
}
int main()
{
  /*测试用例1*/
  // 1 3 5 7       2 4 6 8
  ListNode* Node1 = CreateNode(1);
  ListNode* Node3 = CreateNode(3);
  ListNode* Node5 = CreateNode(5);
  ListNode* Node7 = CreateNode(7);
  ListNode* Node2 = CreateNode(2);
  ListNode* Node4 = CreateNode(4);
  ListNode* Node6 = CreateNode(6);
  ListNode* Node8 = CreateNode(8);
  connect(Node1, Node3);
  connect(Node3, Node5);
  connect(Node5, Node7);
  connect(Node2, Node4);
  connect(Node4, Node6);
  connect(Node6, Node8);
  cout << "链表1:";
  PrintList(Node1);
  cout << "链表2:";
  PrintList(Node2);
  ListNode* head = Merge(Node1, Node2);
  cout << "合并后的链表：";
  PrintList(head);
  cout << "--------------------------------------" << endl;
  /*测试用例2*/
  // 1 2 4      3 5 8  
  Node1 = CreateNode(1);
  Node2 = CreateNode(2);
  Node4 = CreateNode(4);
  Node3 = CreateNode(3);
  Node5 = CreateNode(5);
  Node8 = CreateNode(8);
  connect(Node1, Node2);
  connect(Node2, Node4);
  connect(Node3, Node5);
  connect(Node5, Node8);
  cout << "链表1:";
  PrintList(Node1);
  cout << "链表2:";
  PrintList(Node3);
  head = Merge(Node1, Node3);
  cout << "合并后的链表：";
  PrintList(head);
  return 0;
}

如果我们可以修改原链表，代码将更加简单。由于只修改了Merge函数，所以展示部分代码

C++

ListNode* Merge(ListNode* pHead1, ListNode* pHead2)//合并俩链表
{
  if (nullptr == pHead1)
  {
    return pHead2;
  }
  if (nullptr == pHead2)
  {
    return pHead1;
  }
  ListNode* p1 = pHead1;
  ListNode* p2 = pHead2;
  ListNode* head = new ListNode();//新链表的表头指针
  head->m_nValue = 0;
  head->m_pNext = nullptr;
  ListNode* previously = head;//表尾指针
  while (p1 != nullptr && p2 != nullptr)
  {
    if (p1->m_nValue < p2->m_nValue)
    {
      connNewNode(&previously, &p1);
    }
    else
    {
      connNewNode(&previously, &p2);
    }
  }
  /*可修改原链表的代码*/
  if (p1 != nullptr)
  {
    previously->m_pNext = p1;
  }
  /*可修改原链表的代码*/
  if (p2 != nullptr)
  {
    previously->m_pNext = p2;
  }
  return head->m_pNext;
}

本章完！

剑指Offer - 面试题25：合并俩个排序的链表

分析

热门文章

最新文章

相关课程

相关电子书