逆转单向链表看这一篇就够了【JAVA】

逆转单向链表

逆转前: 1 -> 2 -> 3 -> 4 -> 5 -> null

逆转后: 5 -> 4 -> 3 -> 2 -> 1 -> null

方法一、循环迭代

public Node reverse(Node head) {

        if (head == null || head.next == null) {

            return head;

        }

        // 取前面节点

        Node pre = head;

        // 取后面节点

        Node cur = head.next;

        // 临时节点

        Node temp = null;

        while (cur != null) {

            // 1. 保存后节点的指向节点 因为要替换后节点的指向节点为他的前节点

            temp = cur.next;

            // 2. 把后节点的指向的节点替换成前节点

            cur.next = pre;

            // 下一轮要替换的前节点和后节点

            // 第一次 pre = 1 cur =2  || 那第二次 就得 pre = 2 cur = 3

            pre = cur;

            cur = temp;

        }

        // 在上述过程中未替换首节点的指向节点　这里首节点将成为尾节点　所以指向null

        head.next = null;

        // 因为循环的条件是cur是否为null 如果cur为null 那 pre将是原来链表的尾节点

        // 就是逆转后的首节点

        return cur;

    }

方法二:递归

public Node recursionNode(Node head) {

         if (head == null || head.next == null) {

            return head;

        }

        // head 1 2 3 4

        Node node = reverseNode(head.next);

        // 展示顺序 head 4 3 2 1

        // 第一轮：

        // 当前指向顺序 4 -> 5

        head.next.next = head; // 变成了 5 -> 4 但是4的指针仍然指向5 也就是双向的

        // 所以 4 -> null 变成单向

        head.next = null;

        // node是最后一个元素 5 也就是逆转后的 第一个元素

        return node;

    }