链表之反转链表

力扣链接

题目描述

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例：

​ 输入: 1->2->3->4->5->NULL
​ 输出: 5->4->3->2->1->NULL

限制：

​ 0 <= 节点个数 <= 5000

解题思路

方法一：

遍历链表，并在访问各节点时修改 next 引用指向，使其指向前一个节点

复杂度分析：

时间复杂度 O(N) ： 遍历链表使用线性大小时间
空间复杂度 O(1) ： 变量 pre 和 cur 使用常数大小额外空间

方法二：

使用递归法遍历链表，当越过尾节点后终止递归，尾节点就是反转后的头节点，在回溯时修改各节点的 next 引用指向

• reverseList(head) 函数：

  • 调用并返回 recur(head, null) 。传入 null 是因为反转链表后， head 节点指向 null ；

• recur(cur, pre) 递归函数

  • 终止条件：当 cur 为空，则返回尾节点 pre （即反转链表的头节点）；
  • 递归后继节点，记录返回值（即反转链表的头节点）为 res ；
  • 修改当前节点 cur 引用指向前驱节点 pre ；
  • 返回反转链表的头节点 res ；

---

假如链表1->2->3->4->5->NULL
recur(head,NULL)->recur(2,1)->recur(3,2)->recur(4,3)->recur(5,4)->recur(NULL,5)

---

此时res为5->NULL,cur指向5,pre指向4，反转，使5指向4，再返回res【5->4->NULL】<-回溯<-此时返回节点5 后续步骤同理，最后res为5->4->3->2->1->NULL

---

复杂度分析：

时间复杂度 O(N) ： 遍历链表使用线性大小时间。
空间复杂度 O(N) ： 遍历链表的递归深度达到 N，系统使用 O(N)大小额外空间。

代码实现

#include <iostream>using namespace std;struct ListNode{int val;ListNode* next;ListNode(int x) : val(x),next(NULL){} 
};class Solution{
public://方法一：迭代（双指针） ListNode* reverseList(ListNode* head) {if(head==NULL || head->next==NULL)return head;else{ListNode* pre = NULL;ListNode* cur = head;ListNode* tmp = NULL;//暂存后继节点cur->next while(cur!=NULL){		tmp = cur->next;	//保存下一个节点 cur->next= pre;		//让当前节点指向上一个节点 pre = cur;			//pre暂存cur cur = tmp;			//cur移动到下一个节点 }						//直到cur为空，此时cur从最后一个节点往后移到NULL,而pre移到了最后一个节点 return pre;}}//方法二 递归ListNode* reverseList2(ListNode* head){if(head==NULL||head->next == NULL){return head;} elsereturn recur(head,NULL);}ListNode* recur(ListNode* cur,ListNode* pre){if(cur == NULL) return pre;else{ListNode* res = recur(cur->next,cur);cur->next = pre;return res;}}//链表打印函数void ListPrint(ListNode* head){ListNode* p = head;while(p){cout<<p->val<<"->";p = p->next;}cout<<"NULL"<<endl;}//尾部添加节点void ListPushBack(ListNode **pphead,int val){ListNode* newNode = new ListNode(val);if(*pphead==NULL)*pphead = newNode;else{ListNode* tail = *pphead;while(tail->next){tail = tail->next;}tail->next = newNode;}}
};int main(){ListNode* test = new ListNode(1);ListNode* re;class Solution s;s.ListPushBack(&test,2);s.ListPushBack(&test,3);s.ListPushBack(&test,4);s.ListPushBack(&test,5);
//	s.ListPushBack(&test,6);s.ListPrint(test);re = s.reverseList(test);s.ListPrint(re);return 0;
}

结果：

参考题解：https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/solutions/476929/jian-zhi-offer-24-fan-zhuan-lian-biao-die-dai-di-2/