剑指 Offer 24. 反转链表

剑指offer最优解 5月前 0 190

本问题对应的 leetcode 原文链接：剑指 Offer 24. 反转链表
本文对应打卡链接：【链表专题】剑指 Offer 24. 反转链表

问题描述

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

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

解题思路

视频讲解直达：本题视频讲解

代码实现

方法一：原地反转
时间复杂度：O(N)
额外空间复杂度 O(1)

class Solution {
    // 原地反转
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }

        ListNode cur = head, pre = null;

        while(cur != null){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }

        return pre;

        // 额外空间复杂度=1
    }
}

方法2：递归
时间复杂度：O(N)
额外空间复杂度 O(n)，递归调用需要消耗栈空间

  // 递归
      public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        // 反转子链表
        ListNode temp = reverseList(head.next);
        head.next.next = head;
        head.next = null;

        return temp;
    }

剑指offer题解

class Solution { public: ListNode* reverseList(ListNode* head) { // 链表为空 if (head == nullptr) { return nullptr; } // ListNode* cur = head; ListNode* pre = nullptr; while (cur != nullptr) { ListNode* temp = cur->next; cur->next = pre; pre = cur; cur = temp; } return pre; } };

发表回复取消回复

后才能评论

杨帆普通 2022年11月1日下午4:33

public ListNode reverseList(ListNode head) {
if(head null){
return null;
}
ListNode pre = null;
ListNode cur = head;
ListNode post = head.next;
while(cur.next != null){
cur.next = pre;
pre = cur;
cur = post;
post = post.next;
}
cur.next = pre;
return cur;
}

时间复杂度：O(N)
额外空间复杂度 O(1)

登录以回复

Edison 普通 2022年10月23日下午9:38

原地反转链表

问题描述

解题思路

代码实现

发表回复 取消回复

评论(2)

发表回复取消回复