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