当前位置 博文首页 > Inmaturity_7的博客：算法练习帖--71--反转链表(C语言)
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
（题目来源：力扣官网）
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
限制：
0 <= 节点个数 <= 5000
1.头插法
struct ListNode* reverseList(struct ListNode* head){
if(head==NULL||head->next==NULL){//判断链表长度若为0或1则直接返回head
return head;
}
struct ListNode* temp=head->next;//临时中间结点
head->next=NULL;//头结点初始指向NULL
while(temp!=NULL){
struct ListNode* cur=temp;//获取当前结点
temp=temp->next;//获取下一结点
cur->next=head;//将头结点拼接在当前结点之后
head=cur;//赋值新的头结点
}
return head;
}
2.迭代法（官方题解）
struct ListNode* reverseList(struct ListNode* head){
struct ListNode* pre=NULL;//前一个结点
struct ListNode* cur=head;//当前结点
while(cur){//当前结点不为NULL时
struct ListNode* next=cur->next;//下一节点
//三结点更新
cur->next=pre;
pre=cur;
cur=next;
}
return pre;
}
3.递归法(官方题解)
struct ListNode* reverseList(struct ListNode* head) {
if (head == NULL || head->next == NULL) {//递归中止条件
return head;
}
struct ListNode* newHead = reverseList(head->next);//新头结点
head->next->next = head;//反转当前head结点和head->next的指向
head->next = NULL;//将head->next断链，防止成环
return newHead;
}
