链表 linkList如何实现反转？

Python013

链表 linkList如何实现反转？,第1张

struct List

{

int data

List* next

}

List* ReverseList(List* oldList,List* newHead=NULL)

{

List* next=oldList->next

oldList->next=newHead

newHead=oldList

return (next==NULL) ? newHead : ReverseList(next,newHead)

}

这个简单，只要想想就能写出来。

#include <iostream>

using namespace std

struct Node

{

 int data

 Node *next

}

struct Node *create(int n)

{

 Node *head=NULL,*p

 int i=0

 int d

 while(i<n)

 {

  p=new (struct Node)

     scanf("%d",&p->data)

  p->next=NULL

  if(head==NULL)

    head=p

  else

  {

     p->next=head

     head=p 

  }     

   i++

 }

 return head

}

void show(Node *h)

{

 Node *p

 p=h

 while(p!=NULL)

 {

  printf("%d\t",p->data)

  p=p->next

 }

    printf("\n")

}

struct Node * reverse(struct Node *h)

{

 struct Node *p,*q,*head

 p=h

 int count=0

 while(p->next!=NULL)

   { p=p->next count++}  //找到最后一个节点，并计算节点个数 

 head=p   //翻转的链表的头 

// head->next=NULL

   while(count>0)

   {

      q=h

   while(q->next!=p && q!=NULL)

   {

  q=q->next 

     }      // 找到翻转的链表的尾节点 

   p->next=q

  // q->next=NULL

      p=q

   if(q==h)

     q->next=NULL

      count--

    }

 return head

}

int main()

{

 Node *h1,*h2

 h1=create(8)

 show(h1)

 h2=reverse(h1)

 show(h2)

 return 0

}

正解来了：

typedef struct LIST {

int count

NODE* head

} LIST

typedef struct NODE {

void* data

NODE* next

} Node

/* 链表有头节点 */

void List_Reverse(List *list) {

Node *curr = list->head->next

while (curr) {

Node *next = curr->next

curr->next = list->head

list->head = curr

curr = next

}

}

/* 链表无头节点，所以第一个节点必须也参与反序 */

void List_Reverse(Node **list) { // 注意：参数是指针的指针

Node *head = *list

if (head == NULL) { // 对空链表的保护

return

}

Node *curr = head->next

while (curr) {

Node *next = curr->next

curr->next = head

head = curr

curr = next

}

}