206.反转链表

LeetCode LeetCode 热题100 链表 递归
发布时间 :
字数:1.9k 阅读 : 评论:
  1. 206.反转链表
    1. 206.1 题目
    2. 206.2 题解
      1. 方法一：迭代法
        1. 思路
        2. 复杂度分析
        3. 代码
      2. 方法二：递归法
        1. 思路
        2. 复杂度分析
        3. 代码
    3. 206.3 代码
    4. 206.4 运行结果

206.反转链表

206.1 题目

给你单链表的头节点 head，请你反转链表，并返回反转后的链表。

示例 1：

链表示例

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：
链表示例
输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

进阶：

链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

206.2 题解

方法一：迭代法

思路

反转链表就是让每个节点的 next 指针掉头指向前面。

用三个指针配合：pre 指向前一个节点，cur 指向当前节点，nextTemp 保存下一个节点。

核心操作就四步：

  1. 保存下一个节点
  2. 当前节点指向前一个节点
  3. 前一个节点后移
  4. 当前节点后移

举个例子：1 → 2 → 3 → null

  • 初始：pre=null, cur=1
  • 第一轮：1指向null，pre=1, cur=2
  • 第二轮：2指向1，pre=2, cur=3
  • 第三轮：3指向2，pre=3, cur=null
  • 循环结束，返回pre=3
  • 结果：3 → 2 → 1 → null

复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

代码

// 方法一：迭代法反转链表
// 遍历链表，依次将当前节点的 next 指针指向前一个节点，实现链表反转
static ListNode ReverseList1(ListNode head)
{
    // 如果链表为空或只有一个节点，直接返回原链表头节点
    if (head == null || head.next == null)
        return head;

    // 初始化前一个节点为 null，当前节点为链表头节点
    ListNode pre = null;
    ListNode cur = head;

    // 遍历链表节点
    while (cur != null)
    {
        // 临时变量存储当前节点的下一个节点
        ListNode nextTemp = cur.next;

        // 反转当前节点的指针方向，指向前一个节点
        cur.next = pre;

        // 前一个节点后移
        pre = cur;

        // 当前节点后移
        cur = nextTemp;
    }

    // 循环结束后，pre 指向反转后的链表头节点
    return pre;
}

方法二：递归法

思路

递归的精髓：先递归到链表末尾，然后在回溯过程中修改指针。

对于当前节点 head，先递归处理 head.next，得到反转后的头节点。然后让 head.next.next 指向 head，实现反转。

最后把 head.next 置空，因为它现在是尾节点了。

举个例子：1 → 2 → 3 → null

  • 递归到3，返回3
  • 回溯到2：让3指向2，2指向null，返回3
  • 回溯到1：让2指向1，1指向null，返回3
  • 结果：3 → 2 → 1 → null

复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)，递归栈

代码

// 方法二：递归法反转链表
// 递归到链表末尾，然后回溯过程中修改节点的 next 指针实现链表反转
static ListNode ReverseList2(ListNode head)
{
    // 递归终止条件：链表为空或只有一个节点
    if (head == null || head.next == null)
    {
        return head;
    }

    // 递归调用反转后的链表的头结点 比如12345 到了第4层会返回reversed为5 当前head是4
    ListNode reversed = ReverseList2(head.next);

    // 修改当前节点的 next 指针，使其指向当前节点，实现链表反转
    // 比如12345 到了第4层head是4 head.next是5 head.next.next就是让5指向4
    head.next.next = head;

    //当前head就指向空了 因为其他节点会限制
    head.next = null;

    return reversed; // 反转后的链表头节点为 reversed
}

206.3 代码

using System;

class ListNode
{
    public int val;
    public ListNode next;

    public ListNode(int val = 0, ListNode next = null)
    {
        this.val = val;
        this.next = next;
    }
}

class Program
{
    static void Main()
    {
        #region 题目

        // 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
        // 示例 1：
        // 输入：head = [1,2,3,4,5]
        // 输出：[5,4,3,2,1]
        // 示例 2：
        // 输入：head = [1,2]
        // 输出：[2,1]
        // 示例 3：
        // 输入：head = []
        // 输出：[]
        // 提示：
        // 链表中节点的数目范围是 [0, 5000]
        // -5000 <= Node.val <= 5000
        // 进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

        #endregion

        #region 测试

        // 示例 1
        ListNode head1 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
        Console.WriteLine("示例1 原链表：");
        PrintList(head1);
        ListNode reversed1 = ReverseList1(head1);
        Console.WriteLine("示例1 方法1 反转后的链表：");
        PrintList(reversed1);
        ListNode head1_2 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
        Console.WriteLine("示例1 原链表：");
        PrintList(head1_2);
        ListNode reversed1_2 = ReverseList2(head1_2);
        Console.WriteLine("示例1 方法2 反转后的链表：");
        PrintList(reversed1_2);

        // 示例 2
        ListNode head2 = new ListNode(1, new ListNode(2));
        Console.WriteLine("示例2 原链表：");
        PrintList(head2);
        ListNode reversed2 = ReverseList1(head2);
        Console.WriteLine("示例2 方法1 反转后的链表：");
        PrintList(reversed2);
        ListNode head2_2 = new ListNode(1, new ListNode(2));
        Console.WriteLine("示例2 原链表：");
        PrintList(head2_2);
        ListNode reversed2_2 = ReverseList2(head2_2);
        Console.WriteLine("示例2 方法2 反转后的链表：");
        PrintList(reversed2_2);

        // 示例 3
        ListNode head3 = null;
        Console.WriteLine("示例3 原链表：");
        PrintList(head3);
        ListNode reversed3 = ReverseList1(head3);
        Console.WriteLine("示例3 方法1 反转后的链表：");
        PrintList(reversed3);
        ListNode head3_2 = null;
        Console.WriteLine("示例3 原链表：");
        PrintList(head3_2);
        ListNode reversed3_2 = ReverseList2(head3_2);
        Console.WriteLine("示例3 方法2 反转后的链表：");
        PrintList(reversed3_2);

        #endregion
    }

    #region 答案

    // 方法一：迭代法反转链表
    // 遍历链表，依次将当前节点的 next 指针指向前一个节点，实现链表反转
    static ListNode ReverseList1(ListNode head)
    {
        // 如果链表为空或只有一个节点，直接返回原链表头节点
        if (head == null || head.next == null)
            return head;

        // 初始化前一个节点为 null，当前节点为链表头节点
        ListNode pre = null;
        ListNode cur = head;

        // 遍历链表节点
        while (cur != null)
        {
            // 临时变量存储当前节点的下一个节点
            ListNode nextTemp = cur.next;

            // 反转当前节点的指针方向，指向前一个节点
            cur.next = pre;

            // 前一个节点后移
            pre = cur;

            // 当前节点后移
            cur = nextTemp;
        }

        // 循环结束后，pre 指向反转后的链表头节点
        return pre;
    }


    // 方法二：递归法反转链表
    // 递归到链表末尾，然后回溯过程中修改节点的 next 指针实现链表反转
    static ListNode ReverseList2(ListNode head)
    {
        // 递归终止条件：链表为空或只有一个节点
        if (head == null || head.next == null)
        {
            return head;
        }

        // 递归调用反转后的链表的头结点 比如12345 到了第4层会返回reversed为5 当前head是4
        ListNode reversed = ReverseList2(head.next);

        // 修改当前节点的 next 指针，使其指向当前节点，实现链表反转
        // 比如12345 到了第4层head是4 head.next是5 head.next.next就是让5指向4
        head.next.next = head;

        //当前head就指向空了 因为其他节点会限制
        head.next = null;

        return reversed; // 反转后的链表头节点为 reversed
    }




    #endregion

    #region 辅助方法

    // 打印链表
    static void PrintList(ListNode head)
    {
        ListNode current = head;

        while (current != null)
        {
            Console.Write($"{current.val} -> ");
            current = current.next;
        }

        Console.WriteLine("null");
    }

    #endregion
}

206.4 运行结果

示例1 原链表：
1 -> 2 -> 3 -> 4 -> 5 -> null
示例1 方法1 反转后的链表：
5 -> 4 -> 3 -> 2 -> 1 -> null
示例1 原链表：
1 -> 2 -> 3 -> 4 -> 5 -> null
示例1 方法2 反转后的链表：
5 -> 4 -> 3 -> 2 -> 1 -> null
示例2 原链表：
1 -> 2 -> null
示例2 方法1 反转后的链表：
2 -> 1 -> null
示例2 原链表：
1 -> 2 -> null
示例2 方法2 反转后的链表：
2 -> 1 -> null
示例3 原链表：
null
示例3 方法1 反转后的链表：
null
示例3 原链表：
null
示例3 方法2 反转后的链表：
null
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏