链表逆序的笔试题

题目出处：http://blog.rainbud.net/article/entry20050928-014721
给定一单链表的表头指针和指向其中一个节点的指针，要求以该指针为头将原链表逆序排列，例如：
1. N1->N2->N3->N4->N5->NULL  pHEAD = N1，pSTART = N3，返回N3->N2->N1->N5->N4->NULL
2. N1->N2->N3->N4->N5->NULL  pHEAD = N1，pSTART = N5，返回N5->N4->N3->N2->N1->NULL
3. N1->N2->N3->N4->N5->NULL  pHEAD = N1，pSTART = N1，返回N1->N5->N4->N3->N2->NULL

不允许额外分配存储空间，不允许递归，可以使用临时变量。
很容易想到的做法是先将整个链表逆序，然后将尾节点连接到头节点，然后再从pSTART后面断开。我是把它分成两个部分，即包括pSTART的前面部分和不包括pSTART的后面部分。当pSTART和pHEAD重合时，前面一部分只有一个节点；当pSTART是链表的尾节点的时候，后面一部分是空链表。分别逆序完了以后，再连接起来。

前面有道题说了，使用pHead和两个临时变量就可以将一个链表逆序，我这里没有使用phead,所以用到了三个临时变量。里面用的临时变量比较多，思路不太清晰。

＃i nclude <iostream>
＃i nclude <string> 
using namespace std;

struct Node
{
    char name[3];
    Node * next;
    Node(const char* p)
    {
        strcpy(name,p);
        next=0;
    }
};

//将某个链表逆序
void ReserseList(Node *& pHead, Node *& pTail)
{
    Node *p1=pHead;
    if(p1==0) //首指针为空，表示空链表
{
        pTail=0;
        return;
    }

    Node *p2=p1->next;
    if(p2==0) //首指针的下一个节点为空，表示只有一个节点
{
        pTail=0;
        return;
    }

    //至少有两个不为空的节点
Node *p3=0;
    while(p2!=0)
    {
        p3=p2->next;
        p2->next=p1;
        p1=p2;
        p2=p3;
        p3=0;
    }
    pHead->next=0; //将首节点的next置为0，否则会形成循环链表
pTail=pHead;
    pHead=p1;
}

//分成两个链表，然后再合并
Node * Reserse(Node * pHEAD, Node * pSTART)
{
    Node *ptmp1=pHEAD, *ptmp2=pSTART;

    //将两表拆开
Node *pHead2=pSTART->next;
    pSTART->next=0;

    ReserseList(ptmp1,ptmp2);//逆序前面一部分
Node *ptmp3=0;

    ReserseList(pHead2,ptmp3);//逆序后面一部分

    //合并
if(ptmp2==0)//前面一部分只有一个节点
ptmp1->next=pHead2;
    else//前面一部分有一个以上的节点
ptmp2->next=pHead2;
    return ptmp1;
}

void output(Node * tmp)
{
    while(tmp!=0)
    {
        cout<<tmp->name<<"->";
        tmp=tmp->next;
    }
    cout<<"NULL"<<endl;
}

int main()
{
    Node * pHEAD=new Node("N1");
    Node * p2=new Node("N2");
    Node * p3=new Node("N3");
    Node * p4=new Node("N4");
    Node * p5=new Node("N5");
    pHEAD->next=p2;
    p2->next=p3;
    p3->next=p4;
    p4->next=p5;

    output(pHEAD);
    Node * result=Reserse(pHEAD,p4);
    output(result);

    getchar();
    return 0;
}