逆置单链表顺序逆置 时间复杂度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;    }}

组词