链表合并

╰半夏微凉° 2022-05-10 10:08 178阅读 0赞

> 请编写一段代码，实现两个单向有序链表的合并

输入描述：

> 第一行一个链表，如1 2 3 4 5
> 
> 第二行一个链表，如2 3 4 5 6

输出描述：

> 输出：1 2 2 3 3 4 4 5 5 6

示例1

> 输入
> 
>     1 2 3 4 5 
>     
>     2 3 4 5 6
> 
> 输出
> 
>     1 2 2 3 3 4 4 5 5 6

C++代码实现：

#include <stdio.h>
    #include <malloc.h>
    #include<iostream>
    #include<vector>
    
    using namespace std;
    
    typedef struct node
    {
    	int data;
    	struct node *next;
    }LNode, *LinkList;
    
    LinkList GreatLinkList()
    {
    	LinkList p, r =NULL, list = NULL;
    	int e;
    	int i;
    	vector<int> a;
    	int b;
    	while (cin >> b)
    	{
    		a.push_back(b);
    		if (cin.get() == '\n')
    			break;
    	}
    
    
    	for (i = 0; i < a.size(); i++)
    	{
    		p = (LinkList)malloc(sizeof(LNode));	/*分配一个新的链表结点*/
    		p->data = a[i];
    		p->next = NULL;
    		if (list == NULL)
    		{
    			list = p;			/*list指向第一个结点，list是头指针*/
    		}
    		else
    		{
    			r->next = p;		/*将新结点连接到链表的尾部*/
    		}
    		r = p;						/*指针r始终指向链表的最后一个结点*/
    	}
    	return list;					/*返回链表的头指针*/
    }
    
    LinkList MergeList(LinkList list1, LinkList list2)
    {
    	LinkList list3;
    	LinkList p = list1, q = list2;
    	LinkList r;
    
    	if (list1->data <= list2->data)
    	{
    		list3 = list1;			/*list1的第一个元素最小，list3指向它*/
    		r = list1;				/*指针r指向list1的第一个元素*/
    		p = list1->next;		/*p指向list1的第二个元素*/
    	}
    	else
    	{
    		list3 = list2;			/*list2的第一个元素最小，list3指向它*/
    		r = list2;				/*指针r指向list2第一个元素*/
    		q = list2->next;		/*q指向list2的第二个元素*/
    	}
    
    	while (p != NULL && q != NULL)
    	{
    		if (p->data <= q->data)  /*若当前p指向的结点值不大于q指向的结点值*/
    		{
    			r->next = p;		/*将p所指向的结点链接到r所指向的结点的后面*/
    			r = p;				/*指针后移*/
    			p = p->next;		/*指针后移*/
    		}
    		else
    		{
    			r->next = q;		/*将所指向的结点链接到r所指向的结点的后面q*/
    			r = q;				/*指针后移*/
    			q = q->next;		/*指针后移*/
    		}
    	}
    
    	r->next = p ? p : q;			/*插入剩余结点*/
    	return list3;				/*返回合并后的链表list3，即链表首地址*/
    }
    
    void printLink(LinkList list)
    {
    	while (list != NULL)
    	{
    		printf("%3d", list->data);	/*打印出每个结点中的数据data*/
    		list = list->next;
    	}
    	printf("\n");
    }
    
    int main()
    {
    	LinkList list1, list2, list3;
    
    	list1 = GreatLinkList();	
    	list2 = GreatLinkList();	/*创建一个按值有序的包含10个元素的链表*/
    	list3 = MergeList(list1, list2);
    	printLink(list3);		/*打印出链表的内容*/
    	system("pause");
    	return 0;
    }
    
    
    #include <iostream>   
    #include <string>
    
    using namespace std;
    
    int main()
    {
    	string  ch;
    	int n;
    
    	cin >> ch;
    	cin >> n;
    
    	for (int k = 0; k < ch.size() - n + 1; k++)
    	{
    		for (int i = 0; i < n; i++)
    		{
    			cout << ch[i + k];
    			if ((i + 1) % n == 0)
    				cout << endl;
    		}
    
    	}
    	system("pause");
    	return 0;
    }