合并两个链表 [英] Combining two linked lists

问题描述

我需要帮助来合并和排序2个链接列表

mergeLists()是我尝试完成的功能


我的完整代码如下

I need help to merge and sort 2 link lists

mergeLists() is the function i try to complete


And my full code is below

#include <stdio.h>

typedef struct Node
{
	int element;
	struct Node* next;	
} Node;

Node* mergeLists(Node* list1, Node* list2)
{
}

Node *createList(int x)
{
	Node *tmp;
	tmp =(Node *)malloc(sizeof(Node));
	tmp->element = x;
	tmp->next = NULL;
	return tmp;
}
Node* insertOrdered(Node *head, int x)
{
	Node *tmp;
	
	tmp = head;
	if (head->element > x) // insert at beginning
	{
		tmp = (Node *)malloc(sizeof(Node));
		tmp->element = x;
		tmp->next = head;
		return tmp;
	}
	
	while (tmp->next!=NULL && tmp->next->element <= x)
		tmp = tmp->next;
	if (tmp->next == NULL) // insert at the end 
	{
		tmp->next = (Node *)malloc(sizeof(Node));
		tmp->next->element = x;
		tmp->next->next = NULL;
	}
	else // insert in the middle 
	{
		Node *tmp2 = tmp->next;
		tmp->next = (Node *)malloc(sizeof(Node));
		tmp->next->element = x;
		tmp->next->next = tmp2;
	}
	return head;
}
void printList(Node *head)
{
	Node *tmp;
	tmp = head;
	while (tmp!=NULL)
	{
		printf("%d ",tmp->element);
		tmp = tmp->next;
	}
	printf("\n");
}
int main()
{
	Node *listA;
	Node *listB;
	Node *merged;
	listA = createList(6);
	listB = createList(4);
	
	listA = insertOrdered(listA,3);
	listA = insertOrdered(listA,9);
	listA = insertOrdered(listA,5);
	listA = insertOrdered(listA,10);
	listA = insertOrdered(listA,2);
	listB = insertOrdered(listB,1);
	listB = insertOrdered(listB,8);
	listB = insertOrdered(listB,7);
	listB = insertOrdered(listB,14);
	listB = insertOrdered(listB,11);
	listB = insertOrdered(listB,19);
	listB = insertOrdered(listB,15);

	printList(listA);	
	printList(listB);	
 	merged = mergeLists(listA,listB);
	printList(merged);	
}

谢谢.

Thanks.

推荐答案

好吧，我会讲一些代码，因为(A)我刚刚醒来，而这段代码只是一种快速尝试. (B)我相信学习编程的最好方法是学习其他源代码.但是，请不要仅仅使用代码来尝试了解它在做什么，因为这会使您成为程序员，而不仅仅是粘贴其他代码. :)

Well I will give some code because (A) I just woke up and this code is just a quick attempt. And (B) I believe the best way to learn programming is to study others source code. But please don''t just use the code try to understand what it is doing cause that is what will make you a programmer not just pasting others code ok. :)

Node* mergeLists(Node* list1, Node* list2)
{
	Node *merged = createList(10);

	while(list1 != 0 || list2 != 0)
	{
		if (list1 != 0) 
		{
			merged = insertOrdered(merged, list1->element);
			list1 = list1->next;
		}
		if (list2 != 0) {
			merged = insertOrdered(merged, list2->element);
			list2 = list2->next;
		}
	}
 
    return merged;
}

我也将它们添加到代码的开头，因为我收到错误C3861:" createList":找不到标识符.

also I added these to the start of the code because I was getting error C3861: ''createList'': identifier not found.

void printList(Node *head);
Node* insertOrdered(Node *head, int x);
Node *createList(int x);
Node* mergeLists(Node* list1, Node* list2);

由于这看起来像是一项作业，因此我不会给出真实的代码，但是您需要做的是:

Since this looks like an assignment, I wont give real code, but what you need to do is this:

//Get an iterator of the list and create a new list
Node i1 := list1.head()
Node i2 := list2.head()
Node merge:= new list
While not i1.empty() and not i2.empty()
	//Keep adding from i1 until we reach an element in i2 which is smaller
	While i1 <= i2
		merge.add_at_tail(i1)
		i1 = i1.next()
	End While
	//Now keep adding from i2 until we reach an element in i1 which is smaller
	While i1 >= i2
		merge.add_at_tail(i2)
		i2 = i2.next()
	End While
End While
Return merge

在进行比较之前，您还需要检查自己是否在列表的末尾

You also need to check if you are at the end of the list before you do the comparisons

这篇关于合并两个链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！