数据结构 - 有两个链表，第一个升序，第二个降序，合并为一个升序链表（C++）

#include <iostream>

#define NULL 0

using namespace std;

struct Node
{
	char data;
	Node* next;
};

Node* create()
{
	Node* head = NULL;
	Node* rear = head;
	Node* p; // The pointer points to new created node.
	char tmp;

	do
	{
		cout << "Please input integer or char '#':";
		cin >> tmp;
		if(tmp != '#')
		{
			p = new Node;
			p->data = tmp;
			p->next = NULL;

			if(head == NULL)
			{
				head = p;
			}
			else
			{
				rear->next = p;
			}

			rear = p;
		}
	}
	while(tmp != '#');

	return head;
}

void print(Node* head)
{
	Node* p = head;
	if(head != NULL)
	{
		do
		{
			cout << p->data << ' ';
			p = p->next;
		}
		while(p != NULL);
	}

	cout << endl;
}

Node* reverse(Node*& head) // Use & here since the function body changed the head pointer.
{
	if(head == NULL)
	{
		return NULL;
	}

	Node*pre, *cur, *ne;
	pre = head;
	cur = head->next;
	while(cur)
	{
		ne = cur->next; // Store next pointer.
		cur->next = pre; // Reverse the current code pointer.
		pre = cur;
		cur = ne;
	}

	head->next = NULL;
	head = pre;

	return head;
}

Node* merge(Node* l1, Node* l2)
{
	Node* l2Reverse = reverse(l2);
	Node* p = new Node;
	p->next = NULL;
	Node* q = p;
	while(l1 && l2Reverse)
	{
		if(l1->data < l2Reverse->data)
		{
			p->next = l1;
			l1 = l1->next;
		}
		else
		{
			p->next = l2Reverse;
			l2Reverse = l2Reverse->next;
		}

		p = p->next;
	}

	if(l1)
	{
		p->next = l1;
	}
	else if(l2Reverse)
	{
		p->next = l2Reverse;
	}

	return q->next;
}

void main()
{
	Node* list1 = create();
	cout << "The first list is:";
	print(list1);

	Node* list2 = create();
	cout << "The second list is:";
	print(list2);

	cout << "The merged list is:";
	Node* list = merge(list1, list2);
	print(list);
}

// Output:
/*
Please input integer or char '#':1
Please input integer or char '#':2
Please input integer or char '#':3
Please input integer or char '#':4
Please input integer or char '#':7
Please input integer or char '#':9
Please input integer or char '#':#
The first list is:1 2 3 4 7 9
Please input integer or char '#':8
Please input integer or char '#':6
Please input integer or char '#':5
Please input integer or char '#':4
Please input integer or char '#':2
Please input integer or char '#':1
Please input integer or char '#':#
The second list is:8 6 5 4 2 1
The merged list is:1 1 2 2 3 4 4 5 6 7 8 9
*/