链表翻转 全翻转 部分翻转

秒杀所有链表翻转问题

public class ListReverse {

class Node {

    int val;
    
    Node next;

    public Node(int val) {
        this.val = val;
    }
}

//链表翻转
//递归
public Node reverse(Node head) {
    if (head == null || head.next == null) return head;
    //后续遍历
    Node last = reverse(head.next);
    //将头节点放在其子节点的后面
    head.next.next = head;
    head.next = null;//将原来的头节点分裂
    return last;//新的头节点 在整个递归中 一直都是最后一个节点
}

//循环
public Node reverse2(Node head) {
    if (head == null || head.next == null) return head;
    Node cur;
    Node pre = head;
    while (head.next != null) {
        cur = head.next;//临时变量
        cur.next = pre;

        pre = cur;//将临时变量赋值给pre

        head = head.next;//进行下一个值
    }
    return pre;
}

//翻转前k个节点的
Node lastPart = null;

public Node reverse3(Node head, int n) {
    if (n == 1) {
        //说明这个节点的下一个节点
        lastPart = head.next;
        return head;
    }
    //对于前k的进行返还
    Node node = reverse3(head.next, n - 1);
    head.next.next = head;
    head.next = lastPart;
    return node;
}

//如果是翻转链表中一部分呢
Node lp = null;

public Node reverse4(Node head, int start, int end) {
    //如果是从开始的就是等价于前k个节点翻转
    if (start == 1) return reverse3(head, end);
    //否则就是进行迭代 遍历到start=1
    head.next = reverse4(head.next, start - 1, end - 1);
    return head;
}

/**
 * 变态翻转 给定一个链表 每k个节点进行翻转
 * 思路：对于k个节点内部使用区间翻转
 * 对于剩下节点使用递归
 */
public Node reverse5(Node head, int k) {
    if (head == null) return head;
    Node a, b;//分别表示k区间
    a = b = head;
    for (int i = 0; i < k; i++) {
        if (b == null) return head;//说明不足k个 不用翻转
        b = b.next;
    }
    //进行段内翻转
    Node newHead = reverse4(a, 1, k);
    a.next = reverse5(b, k);
    return newHead;
}

}