剑指Offer——合并两个排序链表

题目：输入两个递增排序的链表，合并两个链表并使新链表依然是有序的
链表定义如下：

typedef struct ListNode{
  int Value;
  ListNode *Next;
} *LinkList;

例子如下：
剑指Offer——合并两个排序链表

首先考虑输入特殊情况。我们假设输入链表如果不为空的话必然有序，也就是说不用判断其有序性。
当输入链表都为空指针，此时返回的链表也需要为空指针。
如果输入链表其中一个为空，那么返回另外一个即可。

代码如下：

LinkList MergeSortList(LinkList L1, LinkList L2){
  if(L1==nullptr&&L2==nullptr) return nullptr;
  else if(L1==nullptr) return L2; 
  else if(L2==nullptr) return L1; 
  else{
    ListNode* Node1 = L1; 
    ListNode* Node2 = L2; 

    LinkList ListResult = nullptr;
    ListNode *NodeResult = nullptr;
    //初始化输出的第一个节点
    if(Node1->Value<=Node2->Value){
      NodeResult = Node1;
      ListResult = NodeResult;
      Node1 = Node1->Next;
    }   
    else{
      NodeResult = Node2;
      ListResult = NodeResult;
      Node2 = Node2->Next;
    }   
    //循环判断两个链表的元素大小
    while(Node1!=nullptr&&Node2!=nullptr){
      if(Node1->Value<=Node2->Value){
        NodeResult->Next = Node1;
        NodeResult = NodeResult->Next;
        Node1 = Node1->Next;
      }
      else{
        NodeResult->Next = Node2;
        NodeResult = NodeResult->Next;
        Node2 = Node2->Next;
      }
    }

    //当有一个链表已经结束时，退出循环，此时将另一个链表拷贝到输出链表末端
    if(Node1==nullptr) NodeResult->Next = Node2;
    else NodeResult->Next = Node1;

    return ListResult;
  }
}

最开始首先判断输入两个链表的有效性。

接下来声明两个指针ListNode* Node1 = L1; ListNode* Node2 = L2; 指向输入链表的第一个元素。

声明ListResult指针，此为输出链表的头指针。
声明NodeResult指针，此为跟踪输出链表的指针。

由于输出链表初始化为空指针，所以首先要确定其第一个元素是L1中还是L2中的。12-21行

当两个链表都还没到尾指针时，判断两者元素的大小，将元素小的节点贴在NodeResult后。

当某一个链表已经结束，将另外一个链表贴在NodeResult后即可。

剑指Offer——合并两个排序链表

相关推荐