关于单链表的一些操作

#include<iostream>
#include<stdlib.h>
#include<stack>
using namespace std;

//链表结构
struct ListNode
{
    int m_nValue;
    ListNode* m_pNext;
};

//创建一个链表结点
ListNode* CreateListNode(int value)
{
    ListNode *pNode=new ListNode();
    pNode->m_nValue=value;
    pNode->m_pNext=NULL;
    return pNode;

}

//遍历链表中的所有结点
void PrintList(ListNode* pHead)
{
    ListNode *pNode=pHead;
    while(pNode!=NULL)
    {
        cout<<pNode->m_nValue<<" ";
        pNode=pNode->m_pNext;
    }
    cout<<endl;
}

//往链表末尾添加结点
void AddToTail(ListNode** pHead,int value)
{
    ListNode* pNew=new ListNode();
    pNew->m_nValue=value;
    pNew->m_pNext=NULL;

    if(*pHead==NULL)
    {
        *pHead=pNew;
    }
    else
    {
        ListNode* pNode=*pHead;
        while(pNode->m_pNext!=NULL)
            pNode=pNode->m_pNext;
        pNode->m_pNext=pNew;
    }

}
//非递归翻转
ListNode* ReverseList(ListNode* pHead)
{
    ListNode* pNode=pHead;//当前结点
    ListNode* pPrev=NULL;//当前结点的前一个结点
    ListNode* pReversedHead=NULL;//反转链表头结点
    while(pNode!=NULL)
    {
        ListNode* pNext=pNode->m_pNext;
        if(pNext==NULL)//如果当前结点的下一个结点为空，那么反转链表的头结点就是当前结点。
            pReversedHead=pNode;

        pNode->m_pNext=pPrev;//当前结点指向前一个结点

        pPrev=pNode;//pPrev和pNode往前移动。
        pNode=pNext;//这里要使用前面保存下来的pNext，不能使用pNode->m_pNext
    }
    return pReversedHead;//返回反转链表头指针。
}

//递归翻转
ListNode * ReverseList2(ListNode * head)
{
    //如果链表为空或者链表中只有一个元素
    if(head==NULL || head->m_pNext==NULL)
        return head;
    else
    {
       ListNode * newhead=ReverseList2(head->m_pNext);//先反转后面的链表
       head->m_pNext->m_pNext=head;//再将当前节点设置为其然来后面节点的后续节点
       head->m_pNext=NULL;
       return newhead;
    }
}
//合并两个有序链表
ListNode *MergeList(ListNode *phead1,ListNode *phead2)
{
    ListNode *phead=NULL;
    ListNode *ptemphead=NULL;

    if(phead1==NULL || phead2==NULL)
    {
        return NULL;
    }
    if(phead1->m_nValue < phead2->m_nValue)
    {
        phead=phead1;
        phead1=phead1->m_pNext;
    }
    else
    {
        phead=phead2;
        phead2=phead2->m_pNext;
    }
    ptemphead=phead;
    while(phead1 && phead2)
    {
        if(phead1->m_nValue < phead2->m_nValue)
        {
            phead->m_pNext=phead1;
            phead1=phead1->m_pNext;
        }
        else
        {
            phead->m_pNext=phead2;
            phead2=phead2->m_pNext;
        }
        phead=phead->m_pNext;
    }
    if(phead1)
    {
        phead->m_pNext=phead1;
    }
    if(phead2)
    {
        phead->m_pNext=phead2;
    }
    return ptemphead;
}

 // 查找单链表中倒数第K个结点
ListNode * RGetKthNode(ListNode * pHead, unsigned int k)
{
    ListNode *ptemphead=pHead;
    if(pHead ==NULL || k==0)
        return NULL;
    while(pHead && k)
    {
        pHead=pHead->m_pNext;
        k--;
    }
    while(pHead)
    {
        pHead=pHead->m_pNext;
        ptemphead=ptemphead->m_pNext;
    }
    return ptemphead;
}
// 获取单链表中间结点，若链表长度为n(n>0)，则返回第n/2+1个结点
ListNode * GetMiddleNode(ListNode * pHead)
{
    ListNode *p1=pHead;
    ListNode *p2=pHead;

    if(pHead==NULL || pHead->m_pNext==NULL)
        return pHead;
    while(p1->m_pNext && p2->m_pNext)
    {
        p1=p1->m_pNext;
        p2=p2->m_pNext;
        if(p2->m_pNext)
            p2=p2->m_pNext;
    }
    return p1;
}
//判断是否有环
bool HasCircle(ListNode * pHead)
{
    ListNode *p1=pHead;
    ListNode *p2=pHead;

    if(pHead==NULL)
        return -1;
    while(p2->m_pNext)
    {
        p1=p1->m_pNext;
        p2=p2->m_pNext;
        if(p2->m_pNext)
            p2=p2->m_pNext;

        if(p1==p2)
            return true;
    }
    return false;
}
// 从尾到头打印链表，使用递归
void RPrintList(ListNode * pHead)
{
    if(pHead==NULL)
    {
        return;
    }
    else
    {
        RPrintList(pHead->m_pNext);
        cout<<pHead->m_nValue<<" ";
    }
}
//判断链表是否相交。如果两个链表相交于某一节点，那么在这个相交节点之后的所有节点都是两个链表所共有的。判断最后一个节点是否相同
bool IsIntersected(ListNode * pHead1, ListNode * pHead2)
{
    ListNode *p1=pHead1;
    ListNode *p2=pHead2;

    while(p1->m_pNext)
        p1=p1->m_pNext;
    while(p2->m_pNext)
        p2=p2->m_pNext;
        return p1==p2;
}
//两个单链表相交的第一个节点
//对第一个链表遍历，计算长度len1，同时保存最后一个节点的地址。
//对第二个链表遍历，计算长度len2，同时检查最后一个节点是否和第一个链表的最后一个节点相同，若不相同，不相交，结束。
//两个链表均从头节点开始，假设len1大于len2，那么将第一个链表先遍历len1-len2个节点，此时两个链表当前节点到第一个相交节点的距离就相等了，然后一起向后遍历，知道两个节点的地址相同。//
ListNode* GetFirstCommonNode(ListNode * pHead1, ListNode * pHead2)
{
    if(pHead1==NULL || pHead2==NULL)
        return NULL;
    int len1,len2;
    int k;
    ListNode *p1=pHead1;
    ListNode *p2=pHead2;
    ListNode *p11=pHead1;
    ListNode *p22=pHead2;
    while(p1->m_pNext)
    {
        p1=p1->m_pNext;
        len1++;
    }
    while(p2->m_pNext)
    {
        p2=p2->m_pNext;
        len2++;
    }

    if(p1!=p2)
        return NULL;
    if(len1>len2)
    {
        k=len1-len2;
        while(k--)
            p11=p11->m_pNext;
    }
    else
    {
        k=len2-len1;
        while(k--)
            p22=p22->m_pNext;
    }
    if(p11!=p22)
    {
        p11=p11->m_pNext;
        p22=p22->m_pNext;
    }
    return p11;
}
//测试程序
int main(int argc,char **argv)
{
    //创建结点
    ListNode* pNode1=CreateListNode(1);//创建一个结点
    ListNode *pNode2=CreateListNode(2);
    ListNode *pNode=NULL;
    ListNode *ptmepNode=NULL;
    //PrintList(pNode1);//打印
    //往链表中添加新结点
    AddToTail(&pNode1,3);//为链表添加一个结点
    AddToTail(&pNode1,6);//为链表添加一个结点
    AddToTail(&pNode1,7);//为链表添加一个结点
    AddToTail(&pNode1,8);//为链表添加一个结点

    AddToTail(&pNode2,4);//为链表添加一个结点
    AddToTail(&pNode2,7);//为链表添加一个结点
    AddToTail(&pNode2,8);//为链表添加一个结点
    AddToTail(&pNode2,10);//为链表添加一个结点
    //打印链表
    //PrintList(pNode1);//打印
    //PrintList(pNode2);

    //反转链表
    //ListNode* pReversedHead=ReverseList(pNode1);
    //ListNode* pReversedHead=ReverseList2(pNode1);
    //PrintList(pReversedHead);

    //合并链表
    //pNode=MergeList(pNode1,pNode2);
    //PrintList(pNode);

    //翻转打印链表
    //RPrintList(pNode);

    //获取倒数第三个链表
    //pNode=RGetKthNode(pNode2,3);
    //cout<<"倒数第三个元素"<<pNode->m_nValue<<endl;

    //获取链表中间元素
    //ptmepNode=GetMiddleNode(pNode);
    //cout<<"中间元素为"<<ptmepNode->m_nValue<<endl;

//判断链表是否存在环

 /* if(HasCircle(pNode))
    {
        cout<<"存在环"<<endl;
    }
    else
    {
        cout<<"不存在环"<<endl;
    }
*/

//判断两个链表是否相交
    if(IsIntersected(pNode1,pNode2))
    {
        cout<<"相交"<<endl;
    }
    else
    {
        cout<<"不相交"<<endl;
    }

    //获取链表相交的第一个节点
    ptmepNode=GetFirstCommonNode(pNode1,pNode2);
    if(ptmepNode==NULL)
    {
        cout<<"不相交"<<endl;
    }
    else
    {
        cout<<"相交第一个点的值"<<ptmepNode->m_nValue<<endl;
    }

    return 0;
}