LeetCode:合并两个有序的链表（c++实现）

90 阅读 0 评论 60 点赞

我是靠谱客的博主高兴手套，最近开发中收集的这篇文章主要介绍LeetCode:合并两个有序的链表（c++实现），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

将两个有序（升序）的链表合并为一个新的有序的链表（c++实现）

问题描述:

现有一个头结点为Ahead的A链表，如1->3->5->7,同时还有一个头结点为Bhead的B链表，如2->4->6->8->10->12。最终要将两者合并成一个新的链表C，如1->2->3->4->5->6->7->8->10->12。

解决思路：

首先创建一个新的头结点，如Chead，作为新链表的头结点（该结点里面的value值可设为0），同时创建一个pre指针来指向Chead头结点（这样就可以保留住Chead头结点）。同时遍历A和B两个链表（移动各自的头结点），然后比较两个头结点指向的数字的大小。比如当前Ahead指向1，Bhead指向2。因为1<2，所以pre指向的下一个结点是Ahead（数字1，pre->next = Ahead），此时继续移动Ahead指针，Bhead保持不动仍指向数字2，pre指针也往前移动一格（pre = pre->next）。此时Ahead指向数字3，Bhead仍指向数字2。因为2<3，所以pre指向的下一个结点是Bhead（数字2，pre->next =Bhead）,然后移动Bhead指针，Ahead指针保持不动仍指向数字3，同样地，pre指针自身也要往前移动一格。就这样，不断地遍历链表A和B，但需要注意的是A和B不一定会同时结束遍历。比如例子中，A肯定要先于B遍历完。那我们势必要将‘多余’的没遍历完的B的剩余部分，接到链表C的后面。（pre->next =Bhead）。反之，若A有剩余，就是pre->next =Ahead.

源代码

#include<iostream>
using namespace std;
//该函数用遍历输出一个链表，输入为链表的头结点
void Traversal_List(ListNode* head)
{
	while(head)
	{
		cout << head->val << ",";
		head = head->next;
	}
}
//类ListNode来表示链表中的结点
class ListNode
{
public:
	int val;
	ListNode* next;
	ListNode(int v) :val(v) { next = NULL; }
};
//主要内容
class Solution
{
public:
	ListNode* Merger_two_sorted_lists(ListNode* Ahead, ListNode* Bhead)
	{
		ListNode new_head(0);
		//new_head 就是之前提过的Chead头结点
		ListNode* pre = &new_head;
		while (Ahead && Bhead)
		{
			if (Ahead->val < Bhead->val)
			{
				pre->next = Ahead;
				pre = pre->next;
				Ahead = Ahead->next;
			}
			else
			{
				pre->next = Bhead;
				pre = pre->next;
				Bhead = Bhead->next;
			}
			
		}
		//如果Ahead不为空，也就是Ahead还没有遍历完，将A中剩余的部分接到链表C后面
		if (Ahead)
		{
			pre->next = Ahead;
		}
		if (Bhead)
		{
			pre->next = Bhead;
		}
		//注意这里的返回值，因为new_head头结点里面存放的值是无关紧要，头结点指向的下一个结点
		//即new_head.next结点开始，存放的才是链表A或B中的值。
		//
		return new_head.next;
	}
};

主函数如下


int main()
{
	
	ListNode a1(1);
	ListNode a2(3);
	ListNode a3(5);
	ListNode a4(7);


	ListNode b1(2);
	ListNode b2(4);
	ListNode b3(6);
	ListNode b4(8);
	ListNode b5(10);
	ListNode b6(12);
	
	

	//链接链表
	a1.next = &a2;
	a2.next = &a3;
	a3.next = &a4;
	a4.next = NULL;

	b1.next = &b2;
	b2.next = &b3;
	b3.next = &b4;
	b4.next = &b5;
	b5.next = &b6;
	b6.next = NULL;

	cout << "链表A：";
	Traversal_List(&a1);
	cout << endl;
	cout << "链表B: ";
	Traversal_List(&b1);
	cout << endl;

	Solution s1;
	ListNode* result = s1.Merger_two_sorted_lists(&a1, &b1);
	cout << "合并后的链表: ";
	Traversal_List(result);
	return 0;
}