有序链表合并

柔情只为你懂 2021-12-15 21:15 299阅读 0赞

## 有序链表合并 ##

#include<stdio.h>
    #include<iostream>
    using namespace std;
    //测试数据
    const int arrrlens = 5;
    int arr_1[arrrlens] = { 9, 7, 5, 3, 1 };
    int arr_2[arrrlens] = { 0, 2, 4, 6, 8 };
    class Node {
    public:
    	//构造函数，创建一个节点
    	Node(int el = NULL, Node* ptr = NULL) {
    		infor = el;
    		next = ptr;
    	}
    	int infor;
    	Node* next;
    };
    class NodeList {
    public:
    	NodeList() {
    		head = new Node();
    	}
    	~NodeList() {
    		delete head;
    	}
    	//节点插入头部
    	void printList();
    	void addToHead();
    	void addToTail();
    	Node* getHead();
    	//Node* mergeTwoOrderLists(NodeList*, NodeList*);
    	
    private:
    	Node* head;
    };
    //头部插入法链表顺序与输入数据顺序相反
    Node* NodeList::getHead()
    {
    	return head;
    }
    void NodeList::addToHead()
    {
    	 
    	for (int i = 0; i < arrrlens; i++)
    	{
    		int node = arr_1[i];
    		Node* p = new Node(node, NULL);
    		if (i == 0) {
    			head = p;
    		}
    		else {
    			p->next = head;
    			head = p;
    		}
    	}
    }
    void NodeList::addToTail()
    { 
    	Node *fp = head;
    	for (int i = 0; i < arrrlens; i++)
    	{
    		int node = arr_2[i];
    		Node* p = new Node(node, NULL);
    		fp->next = p;
    		fp = p;
    	}
    	//删除头部为空节点
    	Node* newHead = head->next;
    	delete head;
    	head = newHead;
    }
    //非递归合并
    Node* mergeTwoOrderLists(Node* pHead1, Node* pHead2)
    {
    	Node* newHead = NULL;
    	Node* pTail = NULL;
    	if (pHead1 == NULL) {
    		return pHead2;
    	}
    	else if (pHead2 == NULL) {
    		return pHead1;
    	}
    	else {
    		//确定头指针,newHead用来索引后面的节点
    		if (pHead1->infor < pHead2->infor) {
    			newHead = pHead1;
    			pHead1 = pHead1->next;
    		}else {
    			newHead = pHead2;
    			pHead2 = pHead2->next;
    		}
    		//pTail一直next直到结束
    		pTail = newHead;
    		while (pHead1 && pHead2)
    		{
    			if (pHead1->infor < pHead2->infor) {
    				pTail->next = pHead1;
    				pHead1 = pHead1->next;
    			}
    			else {
    				pTail->next = pHead2;
    				pHead2 = pHead2->next;
    			}
    			pTail = pTail->next;
    		}
    		if (pHead1 == NULL) {
    			pTail->next = pHead2;
    		}
    		else if (pHead2 == NULL) {
    			pTail->next = pHead1;
    		}
    	}
    	return newHead;
    	return NULL;
    }
    //递归合并有序链表
    Node* __mergeTwoOrderLists(Node* pHead1, Node* pHead2)
    {
    	Node* newHead = NULL;
    	if (pHead1 == NULL) {
    		return pHead2;
    	}
    	else if (pHead2 == NULL) {
    		return pHead1;
    	}
    	if (pHead1->infor < pHead2->infor)
    	{
    		newHead = pHead1;
    		newHead->next = __mergeTwoOrderLists(pHead1->next, pHead2);
    	}else {
    		newHead = pHead2;
    		newHead->next = __mergeTwoOrderLists(pHead1, pHead2->next);
    	}
    	return newHead;
    }
    
    void NodeList::printList()
    {
    	Node* p = head;
    	while (p != NULL)
    	{
    		printf("%d ", p->infor);
    		p = p->next;
    	}
    	printf("\n");
    }
    
    int main()
    {
    	NodeList nlist_1, nlist_2;
    	nlist_1.addToHead();
    	nlist_2.addToTail();
    	nlist_1.printList();
    	nlist_2.printList();
    	//Node* newHead = mergeTwoOrderLists(nlist_1.getHead(), nlist_2.getHead());
    	Node* newHead = __mergeTwoOrderLists(nlist_1.getHead(), nlist_2.getHead());
    	while (newHead != NULL)
    	{
    		printf("%d ", newHead->infor);
    		newHead = newHead->next;
    	}
    	printf("\n");
    }

结果：![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1VwX2p1bmlvcg_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1VwX2p1bmlvcg_size_16_color_FFFFFF_t_70]: /images/20211215/7743686997344a93a673fba0b57df6d8.png