反转链表

递归反转链表的一部分

递归反转整个链表

//1.函数定义：输入一个节点 head，将「以 head 为起点」的链表反转，并返回反转之后的头结点。
ListNode reverse(ListNode head){
    //2.base case
    if(head.next == null){
        return head;
    }
    //3.递归
    ListNode last = reverse(head.next);
    //后序遍历相关操作
    head.next.next = head;
    head.next = null;
    return last;
}

反转链表前n个节点

//后驱节点
ListNode successor = null;
//函数定义：反转以head为起点的n个节点，并返回反转后的头结点
ListNode reverseN(ListNode head,int n){
    //base case
    if(n == 1){
        //记录第n + 1个节点
        successor = head.next;
        return head;
    }
    //以head.next为起点，反转n - 1个节点
    ListNode last = reverseN(head.next,n - 1);
    head.next.next = head;
    head.next = successor;
    return last;
}

反转链表的一部分

//后驱节点
ListNode successor = null;
//函数定义：反转以head为起点的m到n个节点，并返回反转后的头结点
ListNode reverseBetween(ListNode head,int m,int n){
    //base case
    if(m == 1){
        reverseN(head,n);
    }
    //反转以head.next为起点，m-1到n-1个节点，并返回反转后的头结点。向m = 1靠拢
    ListNode last = reverseBetween(head.next,m - 1,n - 1);
    return last;
}

如何k个一组反转链表

迭代的方式反转整个链表

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;
}

迭代的方式反转部分链表

ListNode reverse(ListNode a,ListNode b){
    ListNode pre,cur,nxt;
    pre = null;
    cur = a;
    nxt = b;
    while(cur != b){
        nxt = cur.next;
        cur.next = pre;
        pre = cur;
        cur = nxt;
    }
    return pre;
}

k个一组反转

ListNode reverseKGroup(ListNode head,int k){
    ListNode a,b;
    a = b = head;
    for(int i = 0; i < k; i++){
        if(b == null) return head;
        b = b.next;
    }
    ListNode newHead = reverse(a,b);
    a.next = reverseKGroup(b,k);
    return newHead;
}

如何判断回文链表

//实际上就是把链表的节点放入到方法调用栈，再取出来，就是反转后的链表了
 ListNode left = null;
public boolean isPalindrome(ListNode head) {
    left = head;
    return traverse(head);
}
public boolean traverse(ListNode right){
    if(right == null){
        return true;
    }
    boolean res = traverse(right.next);
    //后序遍历代码
    res = res && (left.val == right.val);
    left = left.next;
    return res;
}