title: 每日一练（13）：反转链表

categories:[剑指offer]

tags:[每日一练]

date: 2022/01/26

每日一练（13）：反转链表

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

示例:

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

限度：

0 <= 节点个数 <= 5000

起源：力扣（LeetCode）

链接：https://leetcode-cn.com/probl...

办法一：双指针

具体过程如下：

假如链表为 1→2→3→∅，咱们想要把它改成∅←1←2←3。

在遍历链表时，将以后节点的 next 指针改为指向前一个节点。因为节点没有援用其前一个节点，因而必须当时存储其前一个节点。在更改援用之前，还须要存储后一个节点。最初返回新的头援用。

复杂度剖析

  • 工夫复杂度：O(n)，其中 n 是链表的长度。须要遍历链表一次。
  • 空间复杂度：O(1)。
ListNode* reverseList(ListNode* head) {        if (head == nullptr) {            return nullptr;        }        ListNode *prev = nullptr;        ListNode *curr = head;//双指针解法        while (curr) {            ListNode *next = curr->next; //保留一下 cur的下一个节点，因为接下来要扭转cur->next            curr->next = prev;    //翻转操作            prev = curr; //更新pre 和 cur指针            curr = next;        }        return prev;}

办法二：递归

复杂度剖析

  • 工夫复杂度：O(n)，其中 n 是链表的长度。须要对链表的每个节点进行反转操作。
  • 空间复杂度：O(n)，其中 n 是链表的长度。空间复杂度次要取决于递归调用的栈空间，最多为 n 层。
ListNode* reverseList(ListNode* head) {    if (!head || !head->next) {        return head;    }    ListNode* newHead = reverseList(head->next);    head->next->next = head;    head->next = nullptr;    return newHead;}