单链表逆转

单链表逆转

 

单链表逆转算法草图如下：

 

方法1：借助辅助空间

建立临时的新链表，将新节点指向其前驱结点实现逆转：

#include <stdio.h>
#include <conio.h>
#include<malloc.h>
//#include "alloc.h"

typedef struct  /* 使用typedef定义类型 */
{
    char x;
    struct node * next;
} node;

node * input()
{
    node *p1,*p2,*h=NULL;
    char ch;
    while(1)
    {
        ch=getche();
        if(ch=='\r') break;
        p1=(node *)malloc(sizeof(node));
        p1->x=ch;
        if(h==NULL) h=p1;
        else p2->next=p1;
        p2=p1;
    }
    p1->next=NULL;
    return h;
}

void display(node *p)
{
    printf("\n");
    while(p!=NULL)
    {
        putchar(p->x);
        p=p->next;
    }
}

node * reverse(node * p)
{
    node * p1=NULL,*p2;
    while(p!=NULL)
    {
        p2=(node *) malloc(sizeof(node));
        if(p1==NULL) p2->next=NULL; /* 逆转之后，原链表的头结点就是新链表的尾结点 */
        else p2->next=p1;    /* 如果不是第一个结点，则本次产生的新结点是上次结点的前一个 */
        p1=p2;
        p2->x=p->x;
        p=p->next;
    }
    return p1;  /*原链表的最后一个结点是新链表的头结点 */
}

int main(void)
{
    node * head,* h2;
    head=input();
    display(head);
    h2=reverse(head);
    display(h2);
    getch();

    return 0;
}

 

方法2：原地逆转

头尾互换，指针指向反转

#include <stdio.h>
#include <conio.h>
#include <malloc.h>

struct node
{   char x;
    struct node * next;
};

struct node * input()
{
    struct node *p1,*p2,*h=NULL;
    char ch;
    while(1)
    {
        ch=getche();
        if(ch=='\r') break;
        p1=(struct node *)malloc(sizeof(struct node));
        p1->x=ch;
        if(h==NULL) h=p1;
        else p2->next=p1;
        p2=p1;
    }
    
    p1->next=NULL;
    return h;
}

void display(struct node *p)
{
    printf("\n");
    while(p!=NULL)
    {
        putchar(p->x);
        p=p->next;
    }
}

struct node * reverse(struct node *h)
{
  struct node *p=h,*q=NULL,*listend=h;
  while(listend->next!=NULL) listend=listend->next;
  
  while(p!=listend)
  {
    h=p->next;
    listend->next=p;
    if(q==NULL) p->next=NULL;
    else p->next=q;
    q=p;
    p=h;
  }
  
  return h;
}

int main(void)
{
  struct node * head;
  head=input();
  head=reverse(head);
  display(head);
  getch();
  
  return 0;
}

 

List_ptr InvertList(List_ptr  head) //原地逆转单链表head
{
  List_ptr p=head,q=NULL,listend=head;
  while(listend->next!=NULL) listend=listend->next;
   
  while(p!=listend)
  {
    head=p->next;
    listend->next=p;
    if(q==NULL) p->next=NULL;
    else p->next=q;
    q=p;
    p=head;
  }
   
  return head;
}

 

思考：

单链表的逆转如上都是采用循环遍历的方法，那应该也可采用递归遍历的方法吧？