微信公众号：路人zhang
扫码关注微信公众号

回复“面试手册”，获取本站PDF版

回复“简历”，获取高质量简历模板

回复“加群”，加入程序员交流群

回复“电子书”，获取程序员类电子书

当前位置： 算法 > 剑指offer > 剑指offer 24.反转链表

剑指offer 24.反转链表

题目描述

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

示例:

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

限制：

0 <= 节点个数 <= 5000

题解 1

(链表,迭代) O(n)

创建一个前驱节点 pre，初始值为 nullptr，使用一个指针 cur 遍历链表

cur 不为空执行以下操作：

  1. 首先需要把当前节点的下一个节点存起来，防止链表断裂
  2. 让当前节点的 next 指向前驱节点
  3. 当前节点指向下一个节点，前驱节点指向当前节点
  4. 循环以上步骤直到当前节点为 nullptr

最终 pre 存的就是翻转后链表的头节点

时间复杂度

只需遍历一遍链表，所以时间复杂度为 O(n)，n 为链表的长度

空间复杂度

O(1)

C++代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        auto cur = head;
        while (cur) {
            auto next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};

Java 代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

Python 代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre = None
        cur = head
        while cur:
            next_node = cur.next
            cur.next = pre
            pre = cur
            cur = next_node
        return pre

题解 2

(链表,递归) O(n)

递归的步骤

  1. 递归出口条件：如果链表为空或链表只有一个节点，则不需要翻转，直接返回头节点即可。
  2. 翻转头节点为 head->next 的链表，得到尾节点 tail，即翻转后链表的头节点（因为以 head->next 为头节点的链表和以 head 为头节点的链表的尾节点是一样的）。
  3. 然后将 head->next 链表的头节点的 next 指向原链表的头节点，head->next->next = head。
  4. 最后将原链表的 next 指向空

最终返回翻转后链表的头节点即 tail

时间复杂度

链表中的每个节点只被遍历一遍，所以时间复杂度为 O(n)，n 为链表的长度

空间复杂度

递归的深度为 n，系统栈的空间复杂度为 O(n)，所以额外空间复杂度为 O(n)

C++代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        auto tail = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return tail;
    }
};

Java 代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode tail = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return tail;
    }
}

Python 代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        tail = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return tail

本文由读者提供，Github地址：https://github.com/tonngw

点击面试手册，获取本站面试手册PDF完整版

剑指offer