Java 链表反转
递归的写法：
//反转 单链表 , 递归写法
private ListNode reverseListNode(ListNode node){
if(node == null || node.next == null){
return node;
}
ListNode cur = reverseListNode(node.next);
node.next.next = node;
node.next = null;
return cur;
} 迭代的写法：迭代：注意指针的移动顺序
三个指针，一个指向头节点，一个指向头节点前一个节点，一个指向头节点后一个节点，这个作为临时节点，防止链表断开。
把cur的指向改变。cur.next = pre;//指向他的前边，但是这样操作了，第二个节点就断开了。所以每次反转时候，要把cur.next 赋值给next(一个临时用的，也就是cur的后一个节点)
进行反转操作后，需要遍历后一个，一直重复反转， 用while. 直到cur 为空 ，这个时候，pre 刚刚好指向原来的尾节点，是新 链表 的头节点，return pre;
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode cur = head;
ListNode precur = null;
while(cur != null){
ListNode next = cur.next;//临时保存
cur.next = precur;//反转指针
//后移迭代,这两个移动顺序很重要，先移动pre, 再移动cur
// cur = next;
// precur = cur;
precur = cur;
cur = next;
}
return precur;//cur == null
}
}
对应题目：206
指定区间链表反转：92
这题之前文章写过，这里一起复习一下
一般的思路，找到区间的左右边界，这两个节点：leftNode , rightNode
然后把链表分为三部分， 左 | 指定区间 | 右
需要反转指定区间的链表，那么用反转链表的方法直接对 第二部分链表反转。
然后把左，右 链表连接起来。
为了能连接起来，需要保存右区间的下一个节点，作为右部分的第一个节点。
左区间的，前一个节点需要保存，最后指向右节点，就是连接上了反转后的链表了
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
// 定义一个dummyHead, 方便处理
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode leftNode = dummyHead;
ListNode rightNode = dummyHead;
while(left > 1){//不是从0开始数，//这里为什么是1 , 因为我从head 前面一位开始数的。我要先找到先驱节点
leftNode = leftNode.next;
left--;
}
//left的前驱节点保留。leftPre
ListNode leftPre = leftNode;
//left的节点
leftNode = leftNode.next;
while(right > 0){ //这里为什么是0 , 因为我从head 前面一位开始数的。
rightNode = rightNode.next;
right--;
}
// 断开后续链表；先保存临时的
ListNode temp = rightNode.next;
rightNode.next = null; // 断开联系
leftPre.next = null; // 断开前驱联系
reverseNode(leftNode);
// 接上前续
leftPre.next = rightNode;
// 接上后续
leftNode.next = temp;
return dummyHead.next; //时间复杂度O（N）, 空间复杂度O（N）
}
private ListNode reverseNode(ListNode head){
//反转一个链表
if(head == null || head.next == null){
return head;
}
ListNode cur = reverseNode(head.next);
head.next.next = head;
head.next = null;
return cur;
}
}
优化空间：
头插法， 把leftNode 后面的元素插到左节点的前一个节点后面。
向后遍历，直到遍历到右节点，把右节点插入到pre 后面，完成指定区间的链表反转。
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
// 定义一个dummyHead, 方便处理
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode pre = dummyHead;
// 找到前驱节点
for (int i = 0; i < left - 1; i++) { // 假如left == 2, i = 0 走1次， pre 指向第一个元素，刚刚好是left == 2 的前一个个
pre = pre.next;
}
// 找到左节点
ListNode leftNode = pre.next;
ListNode next;
// 头插法， 把left 后面的元素插入pre 后面。
for (int i = 0; i < right - left; i++) {
next = leftNode.next; // 临时保存一下，别丢弃了
leftNode.next = next.next;//跳过next , 相当于删除了后一个元素。
next.next = pre.next; // 把left 后面的元素插入pre 后面， 这个时候指向pre.next
pre.next = next; // 把pre的后置指针改变位置， 指向next ,完成一次 头插，，left后面的元素插入pre后面了。
}
return dummyHead.next;
}
}
穿针引线的方法：
先保存后面的节点，
然后改变指针的指向。
ListNode next = leftNode . next ;// 先保存后面的节点，
leftNode . next = next . next ; // 穿针引线
next . next = pre . next ; // 穿针引线 然后改变指针的指向。
pre . next = next; // 穿针引线 然后改变指针的指向。
25. K 个一组翻转链表
[给你小心心]写到这里，竟然花了1h.
已经知道了一个链表怎么反转，这里需要反转k个。
循环k次，找到需要翻转的链表的结尾,这里每次循环要判断end是否等于空,因为如果为空，end.next会报空指针异常。
//如果end==null，即需要翻转的链表的节点数小于k，不执行翻转。
//先记录下end.next,方便后面链接链表
//然后断开链表
//记录下要翻转链表的头节点
//翻转链表, 调用单链表反转方法 ：pre.next指向翻转后的链表。
1->2 变成2->1。 dummy->2->1
//翻转后 头节点变到最后 。通过.next把断开的链表重新链接。
start.next=next;
//将pre换成下次要翻转的链表的头结点的上一个节点。即start
pre=start;
//翻转结束，将end置为下次要翻转的链表的头结点的上一个节点。即start
end=start;
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || head.next == null){
return head;
}
//定义一个假的节点。
ListNode dummy=new ListNode(0);
//假节点的next指向head。
// dummy->1->2->3->4->5
dummy.next=head;
//初始化pre和end都指向dummy。pre指每次要翻转的链表的头结点的上一个节点。end指每次要翻转的链表的尾节点
ListNode pre=dummy;
ListNode end=dummy;
while(end.next!=null){
//循环k次，找到需要翻转的链表的结尾,这里每次循环要判断end是否等于空,因为如果为空，end.next会报空指针异常。
//dummy->1->2->3->4->5 若k为2，循环2次，end指向2
for(int i=0;i<k&&end != null;i++){
end=end.next;
}
//如果end==null，即需要翻转的链表的节点数小于k，不执行翻转。
if(end==null){
break;
}
//先记录下end.next,方便后面链接链表
ListNode next=end.next;
//然后断开链表
end.next=null;
//记录下要翻转链表的头节点
ListNode start=pre.next;
//翻转链表,pre.next指向翻转后的链表。1->2 变成2->1。 dummy->2->1
pre.next=reverseListNode(start);
//翻转后头节点变到最后。通过.next把断开的链表重新链接。
start.next=next;
//将pre换成下次要翻转的链表的头结点的上一个节点。即start
pre=start;
//翻转结束，将end置为下次要翻转的链表的头结点的上一个节点。即start
end=start;
}
return dummy.next;
}
//反转单链表, 递归写法
private ListNode reverseListNode(ListNode node){
if(node == null || node.next == null){
return node;
}
ListNode cur = reverseListNode(node.next);
node.next.next = node;
node.next = null;
return cur;
}
} [白眼]加油：PPPPPPPPP
