206.反转链表

LeetCode LeetCode 链表 递归
发布时间 :
字数:1.6k 阅读 : 评论:
  1. 206.反转链表
    1. 206.1 题目
    2. 206.2 题解
      1. 迭代法反转链表
      2. 递归法反转链表
    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 指针指向前一个节点，实现链表反转
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
}

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-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏