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