剑指Offer——合并两个排序链表
题目:输入两个递增排序的链表,合并两个链表并使新链表依然是有序的
链表定义如下:
typedef struct ListNode{
int Value;
ListNode *Next;
} *LinkList;
例子如下:
首先考虑输入特殊情况。我们假设输入链表如果不为空的话必然有序,也就是说不用判断其有序性。
当输入链表都为空指针,此时返回的链表也需要为空指针。
如果输入链表其中一个为空,那么返回另外一个即可。
代码如下:
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后即可。