备战蓝桥杯————递归反转单链表

    当要求只反转单链表中的一部分时，递归实现确实具有一定的挑战性，但也是可行的。下面我将介绍一种递归实现的方法来反转单链表中的一部分。

一、反转链表

题目描述

    给你单链表的头节点 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

解题思路及代码

1. 基本情况检查： if (head == null || head.next == null) { return head; } 这里首先检查了两个基本情况：
   • 如果链表为空，或者只有一个节点，则无需反转，直接返回头节点 head。
   • 否则，继续执行后续的递归操作。
2. 递归调用： ListNode last = reverse(head.next); 递归调用 reverse 函数，传入当前节点 head 的下一个节点。这一步会一直递归到链表的最后一个节点，并返回最后一个节点作为反转后链表的头结点。
3. 反转操作： head.next.next = head; 在递归的过程中，当递归到链表的最后一个节点时，head 指向原链表中的倒数第二个节点，head.next 指向最后一个节点。这一步将最后一个节点的 next 指针指向倒数第二个节点，实现了反转。
4. 断开原链表与反转后链表的连接： head.next = null; 将原链表的头节点的 next 指针置为 null，断开原链表与反转后链表的连接，确保反转后链表的尾节点指向 null。
5. 返回反转后链表的头结点： return last; 返回反转后链表的头结点 last，它是原链表的尾节点，经过反转后成为新链表的头结点。

通过递归地将链表从头到尾反转，最终得到了反转后的链表

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

结果展示

        反转链表是比较简单的题目，该题目不止一种解法，这里使用递归是为了方便后面回溯搜索等算法学习。