剑指 Offer 24. 反转链表

本问题对应的 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;
    }

发表回复

后才能评论

评论(2)

  • 杨帆 普通 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

    原地反转链表

    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;
        }
    };