本文学习与总结自递归反转链表的一部分
题目
主要是有三道反转链表的题目：
实现反转链表
非递归实现
定义一个pre指针，指向null
定义一个cur指针，指向head
每次都先用temp 记录cur 的下一个节点
然后 cur.next = pre
即
pre < --- cur. temp->val->-val->null
然后 将 cur 指针赋值给 pre
temp 指针赋值给
cur
null < --- pre cur->val->-val->null
然后继续循环，直到cur指向null
此时链表形式为：
null < ---val < --- val <--- pre cur(null)
返回 pre 指针即可
代码：
public ListNode reverseList( ListNode head ) {
if ( head == null ) {
return head;
}
ListNode pre = null;
ListNode cur = head;
while ( cur != null ) {
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
}
/*
1-2-3-4-5
pre-1(head-cur)-2-3
temp=cur.next
pre->1(head-cur)->2(temp)->3
cur.next = pre;
pre<-1(head-cur) 2(temp)->3
pre = cur;
pre<-1(head-cur) 2(temp)->3
null<-1(head-cur-pre) 2(temp)->3
cur = temp
null<-1(head-pre) 2(cur)->3
temp=cur.next
null<-1(head-pre) 2(cur)->3(temp)
cur.next = pre
null<-1(head-pre)<-2(cur) 3(temp)
pre = cur
null<-1(head)<-2(pre-cur) 3(temp)
cur =temp
null<-1(head)<-2(pre) 3(cur)->null
temp=cur.next
null<-1(head-cur)<-2(pre) 3(cur)->null(temp)
cur.next = pre
null<-1(head)<-2(pre)<-3(cur) null(temp)
pre = cur
null<-1(head)<-2()<-3(pre-cur) null(temp)
cur = temp
null<-1(head)<-2()<-3(pre) null(cur)
cur ==null 跳出循环
null<-1(head)<-2()<-3(pre)
return pre
*/
递归实现
ListNode reverse(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode last = reverse(head.next);
head.next.next = head;
head.next = null;
return last;
}
对于递归算法，最重要的就是明确递归函数的定义。具体来说，我们的 reverse 函数定义是这样的：
输入一个节点 head，将「以 head 为起点」的链表反转，并返回反转之后的头结点。
明白了函数的定义，再来看这个问题。比如说我们想反转这个链表：
理解递归
对于整个链表来说，将除了第一个元素以外的元素整体逆置，然后再把逆置后的链表尾部指向第一个元素，第一个元素再指向null。那变完成了整体逆置。
1(head)->2->3->4->5->6->null
使用last 来保持反转后的链表
ListNode last = reverse(head.next);
1(head)---> (null)<-2 <-- 3<-- 4<--5<--6(last)
然后执行
head.next.next = head;
1(head) <---2 <-- 3<-- 4<--5<--6(last)
head.next = null;
null<--1(head) <---2 <-- 3<-- 4<--5<--6(last)
return last 即可
反转链表前 N 个节点
反转前n 节点，相当于在反转过程中要判断当前节点是否需要反转，且反转之后要将链表正确连接，要不然就空指针了。
同理，对于前n个元素，将第2 个元素到 第 n 个元素逆置，然后第二个元素指向第一个元素，第一个元素指向 n+1 个元素，这样就完成了逆置前 n 个元素。
ListNode successor = null; // 后驱节点
// 反转以 head 为起点的 n 个节点，返回新的头结点
ListNode reverseN(ListNode head, int n) {
if (n == 1) {
// 记录第 n + 1 个节点
successor = head.next;
return head;
}
// 以 head.next 为起点，需要反转前 n - 1 个节点
// 递归到最后一层时， head 指向了 第n个元素，需要将head.next （也就是 第n+1 个节点 ）赋值给 successor
ListNode last = reverseN(head.next, n - 1);
head.next.next = head;
// 让反转之后的 head 节点和后面的节点连起来
head.next = successor;
return last;
}
反转链表中的一部分
递归版本
这个递归不太好理解，可以考虑自己手动压栈模拟一下
m==1 其实就是上面 逆置前n个元素的办法
return reverseN(head, n);
如果 m 不等于 1
以 1 2 3 4 5 ，m=2，n=4 模拟一下
结果应该是。1-4-3-2-5
head.next = reverseBetween(head.next, m - 1, n - 1);
此时 m-1=1 n-1=3
下一步进入 reverseN(head, n); n=3
相当于从 2 开始，反转前3个节点
return reverseN(head, n);
返回的是。4-3-2-5
然后 head.next ->4-3-2-5
1-4-3-2-5
代码：
ListNode reverseBetween(ListNode head, int m, int n) {
// base case
if (m == 1) {
return reverseN(head, n);
}
// 前进到反转的起点触发 base case
head.next = reverseBetween(head.next, m - 1, n - 1);
return head;
}
非递归版本
public ListNode reverseList(ListNode head) {
if(head==null)return head;
ListNode pre = null;
ListNode cur = head;
while ( cur!=null ){
ListNode temp = cur.next;
cur.next=pre;
pre = cur;
cur = temp;
}
return pre;
}
public ListNode reverseBetween( ListNode head, int left, int right ) {
if ( head == null || (left == right) ) {
return head;
}
ListNode node = head;
int size = 0;
while ( node != null ) {
size++;
node = node.next;
}
if ( right == size ) {
if ( left == 1 ) {
return reverseList( head );
}
ListNode start = head;
int num = 1;
while ( num < left - 1 ) {
start = start.next;
num++;
}
start.next = reverseList( start.next );
} else {
int n = right - left + 1;
ListNode start = head;
ListNode end = head;
int num = 1;
while ( num < left - 1 ) {
start = start.next;
num++;
}
num = 1;
while ( num < right + 1 ) {
end = end.next;
num++;
}
ListNode pre = null;
ListNode cur = null;
if ( left == 1 ) {
cur = head;
} else {
cur = start.next;
}
while ( cur != null && n > 0 ) {
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
n--;
}
if ( left == 1 ) {
head.next = end;
return pre;
} else {
//System.out.println(pre.val);
ListNode temp = start.next;
//System.out.println(temp.val);
start.next = pre;
temp.next = end;;
}
}
return head;
}
K 个一组翻转链表
先实现一个给定开始节点和结束节点反转链表的函数，假设结束节点是null，那么就是反转整个链表。
反转整个链表
就是
// 反转以 a 为头结点的链表
ListNode reverse(ListNode a) {
ListNode pre, cur, nxt;
pre = null; cur = a; nxt = a;
while (cur != null) {
nxt = cur.next;
// 逐个结点反转
cur.next = pre;
// 更新指针位置
pre = cur;
cur = nxt;
}
// 返回反转后的头结点
return pre;
}
如果结束节点不为空呢？
给定开始节点和结束节点反转链表
将结束节点代入循环内进行判断就可以了：
// 反转以 a 为头结点的链表
ListNode reverse(ListNode a,ListNode b) {
ListNode pre, cur, nxt;
pre = null; cur = a; nxt = a;
while (cur != b) {
nxt = cur.next;
// 逐个结点反转
cur.next = pre;
// 更新指针位置
pre = cur;
cur = nxt;
}
// 返回反转后的头结点
return pre;
}
k 个一组反转
ListNode reverseKGroup(ListNode head, int k) {
if (head == null) return null;
// 区间 [a, b) 包含 k 个待反转元素
ListNode a, b;
a = b = head;
for (int i = 0; i < k; i++) {
// 不足 k 个，不需要反转，base case
if (b == null) return head;
b = b.next;
}
// 反转前 k 个元素
ListNode newHead = reverse(a, b);
// 递归反转后续链表并连接起来
a.next = reverseKGroup(b, k);
return newHead;
}
ListNode reverse(ListNode a, ListNode b) {
ListNode pre, cur, nxt;
pre = null; cur = a; nxt = a;
// while 终止的条件改一下就行了
while (cur != b) {
nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
// 返回反转后的头结点
return pre;
}