55

方法1：用三个指针实现单链表（有头结点）的逆置

void Reverse(HeadList *head)
{if(head==NULL||head->next==NULL||head->next->next==NULL)return ;HeadList *s=NULL;HeadList *p=head->next;HeadList *q=p->next;while(p!=NULL){p->next=s;s=p;p=q;if(q!=NULL){q=q->next;}}head->next=s;//头结点指向尾结点
}

方法2：用两个指针实现单链表（有头结点）的逆置 ，利用head->next代替上面代码的s指针

void Reverse(HeadList *head)
{if(head==NULL||head->next==NULL||head->next->next==NULL)return ;HeadList *p=head->next;HeadList *q=p->next;head->next=NULL;while(p!=NULL){p->next=head->next;head->next=p;p=q;if(q!=NULL){q=q->next;}}
}

方法3：使用递归方法将单链表逆置（无头结点）
使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点
此后，每次函数在返回的过程中，让当前结点的下一个结点的 next 指针指向当前节点
同时让当前结点的 next 指针指向 NULL ，从而实现从链表尾部开始的局部反转
当递归函数全部出栈后，链表反转完成。

ListNode* reverseList(ListNode *head)//单链表逆置
{if(head == NULL || head->next == NULL){return head;}ListNode *newHead = reverseList(head->next);//递归入栈head->next->next = head;//反转指向线路head->next = NULL;//切断原来的指向线路return newHead;//返回新的头结点
}