[数据结构与算法]逆置单链表顺序逆置 时间复杂度O（1），空间复杂度O（1），递归逆置 时间复杂度O（1），空间复杂度O（1）

package com.zjl.dataStract;

/**
 * @Author: Zjl
 * @Date: 2022/3/21 17:20
 */
public class InversionLinkList {


    public static void main(String[] args) {
        Node node1 = new Node(null, 44);
        Node node2 = new Node(node1, 55);
        Node node3 = new Node(node2, 66);
        Node node4 = new Node(node3, 77);
        Node node5 = new Node(node4, 88);
        Node node0 = new Node(node5, 99);


        Node p = node0;
        //原序列
        while (p != null) {
            System.out.print(p.data + " --> ");
            p = p.next;
        }

//        p = inversion(node0);
        p = reInversion(node0);
        //逆转后序列
        System.out.println();
        while (p != null) {
            System.out.print(p.data + " --> ");
            p = p.next;
        }

    }

    /**
     * 节点结构
     */
    public static class Node {

        public Node(Node next, Integer data) {
            //指针域
            this.next = next;
            //数据域
            this.data = data;
        }

        //指针域
        public Node next;
        //数据域
        public Integer data;

    }


    /**
     * 简单逆置
     * 时间复杂度 O（n）
     * 空间复杂度O（1）
     * @param node
     * @return
     */
    public static Node inversion(Node node) {

        //开始指向首节点
        Node p = node;
        //指向首个节点 next
        Node q = p.next;
        p.next = null;
        //临时变量
        Node t;

        while (q != null) {
            t = q.next;
            q.next = p;
            p = q;
            q = t;
        }
        return p;
    }

    /**
     * 递归
     * 先递归再回溯
     * 时间复杂度O（n）
     * 空间复杂度O（1）
     * @param node
     * @return
     */
    public static Node reInversion(Node node) {
        if (node == null || node.next == null) {
            return node;
        }
        Node inversionNode = reInversion(node.next);
        node.next.next = node;
        node.next = null;
        return inversionNode;
    }


}