一、反转整个链表
问题:定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
//单链表的实现结构
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x;}
}
反转链表利用迭代不难实现,如果使用递归则有些许难度。
首先来看源码实现:
ListNode reverse(ListNode head) {
if(head == null || head.next == null)
return head;
ListNode ret = reverse(head.next);
head.next.next = head;
head.next = null;
return ret;
}
是否看起来不知所云,而又被这如此简洁的代码所震撼?让我们一起探索一下其中的奥秘。
对于递归算法,最重要的是明确递归函数的定义。
我们的 reverse
函数的定义如下:
输入一个节点 head
,将以 head
为起点的链表反转,并返回反转之后的头节点。
明白了函数的定义后,在来看这个问题。比如我们想反转这个链表
那么输入 reverse(head)
后,会在 ListNode ret = reverse(head.next);
进行递归
不要跳进递归!(你的脑袋能压几个栈呀?)
根据 reverse
函数的定义,函数调用后会返回反转之后的头节点,我们用变量 ret
接收
head.next.next = head;
接下来:
head.next = null;
return ret;
再跳出这层递归就会得到:
神不神奇,这样整个链表就反转过来了!
递归代码就是这么简洁优雅,但要注意两个问题:
1、递归函数要有base case,不然就会一直递归,导致栈溢出
if (head == null || head.next == null) return head;
即链表为空或只有一个节点,直接返回
2、当链表递归反转后,新的头节点为 ret
,而 head
变成了最后一个节点,应该令链表的某尾指向 null
head.next = null;
理解这两个问题之后,我们可以进一步深入研究链表反转的问题,接下来的问题其实均为在这个算法上的扩展。
二、反转链表前N个节点
接下来我们来看这个问题:
问题:反转链表前N个节点,并返回链表头节点
说明:1
Original: https://www.cnblogs.com/Code-CHAN/p/13620048.html
Author: Code-CHAN
Title: 利用递归方法实现链表反转、前N个节点反转以及中间部分节点反转
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/584185/
转载文章受原作者版权保护。转载请注明原作者出处!