当要求只反转单链表中的一部分时,递归实现确实具有一定的挑战性,但也是可行的。下面我将介绍一种递归实现的方法来反转单链表中的一部分。
给你单链表的头节点
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
if (head == null || head.next == null) { return head; }
这里首先检查了两个基本情况:
head
。ListNode last = reverse(head.next);
递归调用 reverse
函数,传入当前节点 head
的下一个节点。这一步会一直递归到链表的最后一个节点,并返回最后一个节点作为反转后链表的头结点。
head.next.next = head;
在递归的过程中,当递归到链表的最后一个节点时,head
指向原链表中的倒数第二个节点,head.next
指向最后一个节点。这一步将最后一个节点的 next
指针指向倒数第二个节点,实现了反转。
head.next = null;
将原链表的头节点的 next
指针置为 null
,断开原链表与反转后链表的连接,确保反转后链表的尾节点指向 null
。
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;
}
}
反转链表是比较简单的题目,该题目不止一种解法,这里使用递归是为了方便后面回溯搜索等算法学习。