递归反转单链表（头插法反转部分链表

要弄pre cur 还有nxt（临时变量保存下一个结点

P0指到需要修改的链表的前一个结点

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy=new ListNode(-1,head);
        ListNode p0=dummy;//指向需要倒转链表的前一个
        for(int i=0;i<left-1;i++){
            p0=p0.next;
        }
        ListNode pre=null,cur=p0.next;
        for(int i=0;i<right-left+1;i++){
            ListNode nxt=cur.next;
            cur.next=pre;
            pre=cur;
            cur=nxt;
        }
        p0.next.next=cur;
        p0.next=pre;
        return dummy.next;

    }
}

K个一组的链表翻转，

在之前的基础上有所变化，先计算链表的长度。

如果长度不够则不翻转

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy=new ListNode(-1,head);
        ListNode p0=dummy;
        ListNode lenp=head;//用于计算链表长度
        ListNode cur=head,pre=null;
        int len=0;
        while(lenp!=null){
            len++;
            lenp=lenp.next;
        }
        while(len>=k){
            len-=k;
            for(int i=0;i<k;i++){
                ListNode nxt=cur.next;
                cur.next=pre;
                pre=cur;
                cur=nxt;
            }
            ListNode temp=p0.next;
            p0.next.next=cur;
            p0.next=pre;
            p0=temp;
        }
        return dummy.next;
        }
    }

如何判断回文链表

寻找回文串的核心思想是从中心向两端扩展

而判断一个字符串是不是回文串就简单很多，不需要考虑奇偶情况，只需要双指针技巧，从两端向中间逼近即可：

1用递归

用快慢指针先找到链表的中间值，再反转中间值后面的链表进行比较。

class Solution {
    ListNode left;
    public boolean isPalindrome(ListNode head) {
        left=head;
        return travers(head);
    }
    boolean travers(ListNode right){
        if(right==null) return true;
        boolean res=travers(right.next);
        res=res&&(right.val==left.val);
        left=left.next;
        return res;
    }
}

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow=head,fast=head;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        if(fast!=null) slow=slow.next;//奇数链表，slow往前走一步
        slow=reverse(slow);//翻转后要更新
        ListNode p1=head,p2=slow;
        while(p2!=null&&p1.val==p2.val){
            p1=p1.next;
            p2=p2.next;
        }
        return p2==null;
    }
    ListNode reverse(ListNode slow){
        ListNode pre=null,cur=slow;
        while(cur!=null){
            ListNode temp=cur.next;
            cur.next=pre;
            pre=cur;
            cur=temp;
        }
        return pre;//返回到翻转后的头结点
    }
}