剑指 Offer 24. 反转链表

本问题对应的 leetcode 原文链接:剑指 Offer 24. 反转链表

问题描述

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

示例 1:

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

限制:

  • 0 <= 节点个数 <= 5000

解题思路

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

代码实现

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
    }

  // 递归
      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;
    }
}

发表回复

后才能评论