本文共 1418 字,大约阅读时间需要 4 分钟。
题目描述 输入一个链表,反转链表后,输出新链表的表头。示例1 输入 { 1,2,3} 返回值 { 3,2,1}
博客图片来自于,本系列博客仅为记录自己的刷题
考虑遍历链表,并在访问各节点时修改 next 引用指向,算法流程见注释。
复杂度分析:
时间复杂度 O(N)O(N) : 遍历链表使用线性大小时间。 空间复杂度 O(1)O(1) : 变量 pre 和 cur 使用常数大小额外空间。初始化
每次循环的操作
/*struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { }};*/class Solution { public: ListNode* ReverseList(ListNode* pHead) { ListNode *res=nullptr,*cur=pHead; while(cur!=nullptr){ ListNode *tmp=cur->next; cur->next=res; res=cur; cur=tmp; } return res; }};
考虑使用递归法遍历链表,当越过尾节点后终止递归,在回溯时修改各节点的 next 引用指向。
recur(cur, pre) 递归函数:
终止条件:当 cur 为空,则返回尾节点 pre (即反转链表的头节点); 递归后继节点,记录返回值(即反转链表的头节点)为 res ; 修改当前节点 cur 引用指向前驱节点 pre ; 返回反转链表的头节点 res ;reverseList(head) 函数:
调用并返回 recur(head, null) 。传入 null 是因为反转链表后, head 节点指向 null ;复杂度分析:
时间复杂度 O(N)O(N) : 遍历链表使用线性大小时间。 空间复杂度 O(N)O(N) : 遍历链表的递归深度达到 NN ,系统使用 O(N)O(N) 大小额外空间。class Solution { public: ListNode* reverseList(ListNode* head) { return recur(head, nullptr); // 调用递归并返回 }private: ListNode* recur(ListNode* cur, ListNode* pre) { if (cur == nullptr) return pre; // 终止条件 ListNode* res = recur(cur->next, cur); // 递归后继节点 cur->next = pre; // 修改节点引用指向 return res; // 返回反转链表的头节点 }};
转载地址:http://azevi.baihongyu.com/