题目描述

还有可以迭代，就是三个指针，一般可以用迭代就可以用递归做

C++ 代码

#include <iostream>
using namespace std;
typedef struct node 
{
    int data;
    struct node* next;

}node_t,*pnode;

pnode creat(void)
{
    pnode head=new node_t;
    if(NULL == head)  return NULL;
    head->data=-1;
    head->next=NULL;
    return head;
}
void insertnode(pnode head,int Data)
{
    if(NULL==  head)  return ;
    pnode p=new node_t;
    if(NULL ==p)  return ;

    p->next=head->next;
    head->next=p;
    p->data=Data;

}

void mprint(pnode head)
{
    if(NULL ==head||NULL==head->next) return ;
    pnode p=head->next;
    while(p)
    {
        cout<<p->data<<"  ";
        p=p->next;
    }
    cout<<endl;
}
pnode    digui(pnode head)
{
    if(NULL== head|| NULL==head->next)  return head;


    pnode  ans=digui(head->next); 
    head->next->next=head;
    head->next=NULL;
    return ans;
}
void test(pnode head)
{
    pnode p=digui(head);
    pnode q=p;
    while(q->next->next)
    {
        q=q->next;
    }
    q->next=NULL;
    head->next=p;
}
int main()
{
    pnode head=NULL;
    head=creat();

    for(int i=0;i<10;i++) 
        insertnode(head,i+1);

    mprint(head);

    test(head);
    mprint(head);

    return 0;
}