c++中对单链表操作---合并两个链表

   题目很简单：

   输入两个链表(不一定有序)，合并这两个链表并使新链表中的结点是按照递增排序。

   其他不多说，看一下代码：

/*
author：http://blog.csdn.net/richerg85
*/
#include "stdafx.h"
#include <iostream>
using namespace std;

struct ListNode
{
	int m_nValue;
	ListNode *m_pNext;
};

ListNode *MergeTwoList(ListNode *pFirstNodeHead, ListNode *pSecondNodeHead)
{
	if ( pFirstNodeHead == NULL )
		return pSecondNodeHead;
	if ( pSecondNodeHead == NULL )
		return pFirstNodeHead;

	//normal merge
	ListNode *pFirstNode = pFirstNodeHead;
	ListNode *pSecondNode = pSecondNodeHead;
	ListNode *pMergeHead = NULL;
	ListNode *pCurNode = NULL;

	if ( pFirstNode->m_nValue < pSecondNode->m_nValue)
	{
		pMergeHead = pFirstNodeHead;
		pFirstNode = pFirstNode->m_pNext;
		pCurNode = pMergeHead;
	}
	else
	{
		pMergeHead = pSecondNodeHead;
		pSecondNode = pSecondNode->m_pNext;
		pCurNode = pMergeHead;
	}

	while ( pFirstNode!=NULL && pSecondNode != NULL )
	{
		if ( pFirstNode->m_nValue < pSecondNode->m_nValue)
		{
			pCurNode->m_pNext = pFirstNode;
			pCurNode = pFirstNode;
			pFirstNode = pFirstNode->m_pNext;
		}
		else
		{
			pCurNode->m_pNext = pSecondNode;
			pCurNode = pSecondNode;
			pSecondNode = pSecondNode->m_pNext;
		}

		if ( pFirstNode == NULL )
			pCurNode->m_pNext = pSecondNode;
		if ( pSecondNode == NULL )
			pCurNode->m_pNext = pFirstNode;
	}
	return pMergeHead; 
}
int  GetNodeLen(ListNode *pHead)
{
	if ( !pHead )
		return 0;
	ListNode *pCur =pHead;
	int nCnt = 0;
	while ( pCur )
	{
		nCnt++;
		pCur = pCur->m_pNext;
	}
	return nCnt;
}
//bubble sort
void SortNode(ListNode *&pHead)
{
	ListNode *p1 = NULL;
	ListNode *p2 = NULL;
	if ( !pHead )
		return;
	int nCnt = GetNodeLen(pHead);
	for (int i=0; i<nCnt-1; i++)
	{
		p1 = pHead;
		for (int j=0; j<nCnt-i-1; j++)
		{
			p2 = p1->m_pNext;
			if ( p1->m_nValue > p2->m_nValue )
			{
				int k = p1->m_nValue;
				p1->m_nValue = p2->m_nValue;
				p2->m_nValue = k;
			}
			p1 = p1->m_pNext;
		}
	}
}
//insert node
void InsertNode(ListNode *&pHead)
{
	ListNode *pListNode = NULL;
	ListNode *pCurNode = NULL;

	if ( pHead == NULL )
	{
		pHead = new ListNode();
		cin >>pHead->m_nValue;
		if ( pHead->m_nValue == -1 )//-1,end
		{
			pHead = NULL;
			return;
		}
		pHead->m_pNext = NULL;
		pCurNode = pHead;
	}
	while(1)
	{
		pListNode = new ListNode();
		cin >> pListNode->m_nValue;
		if ( pListNode->m_nValue == -1 )
			break;
		pListNode->m_pNext = NULL;
		pCurNode->m_pNext = pListNode;
		pCurNode = pListNode;
	}
}

//print list
void PrintList(ListNode *pHead)
{
	if ( pHead )
	{
		ListNode *pCur = pHead;
		while ( pCur )
		{
			cout << pCur->m_nValue << " ";
			pCur = pCur->m_pNext;
		}
		cout << endl;
	}
}

int main()
{
	ListNode *pFistNode = NULL;
	ListNode *pSecondNode = NULL;
	cout<<"Please input first link:(-1 end)"<<endl;
	InsertNode(pFistNode);
	PrintList(pFistNode);
	cout<<"Please input second link:(-1 end)"<<endl;
	InsertNode(pSecondNode);
	PrintList(pSecondNode);
	cout<<"sort first:"<<endl;
	SortNode(pFistNode);
	PrintList(pFistNode);
	cout<<"sort second:"<<endl;
	SortNode(pSecondNode);
	PrintList(pSecondNode);
	ListNode *pMergeNode = MergeTwoList(pFistNode, pSecondNode);
	cout<<"After merge:"<<endl;
	PrintList(pMergeNode);
	return 0;
}

补充：

单链表逆转

void ReverseList(ListNode *&pHead)
{
	if ( !pHead )
		return;
	ListNode *pPre,*pCur,*pNext;
	pPre = pHead;
	pCur = pPre->m_pNext;
	while ( pCur )
	{
		pNext = pCur->m_pNext;
		pCur->m_pNext = pPre;
		pPre = pCur;
		pCur = pNext;
	}
	pHead->m_pNext = NULL;
	pHead = pPre;
}

说明：*&，为指针的引用

删除一个单向链表的最中间元素，不能使用两次循环(申请两个指针，步长不一样)。

void delMiddle(link *head)
{
    if(head == NULL)
           return;
    else if(head->next == NULL)
    {
            delete head;
            return;
    }
    else
    {
            link *low = head;
            link *fast = head->next;
            while(fast != NULL && fast->next != NULL)
            {   
                       fast = fast->next->next;
                       if(fast == NULL)
                                    break;
                       low = low->next;
            }
            link *temp = low->next;
            low->next = low->next->next;
            delete temp;

    }
}