水题：翻/反转链表

递归和非递归代码如下：

package org.example;

class Node<T> {
    T val;
    Node next;
    public Node(T val) {
        this.val = val;
    }

    public Node(T val, Node next) {
        this.val = val;
        this.next = next;
    }
}
public class ReverseList {
    /**
     * while方式反转
     */
    public static Node reverse(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node reHead = null;
        while (head != null) {
            Node cur = head.next;//定义临时变量cur:下一个节点的值
            head.next = reHead;
            reHead = head;
            head = cur;
        }
        return reHead;
    }
    /**
     * 递归方式反转
     */
    public static Node reverseWithRecursion(Node head) {
        if (head == null || head.next == null)
            return head;
        Node newNode = reverseWithRecursion(head.next);
        head.next.next = head;//
        head.next = null;
        return newNode;
    }

    public static void printList(Node head) {
        if (head == null) {
            return ;
        }
        while (head != null) {
            System.out.print(head.val + "-->");
            head = head.next;
        }
            }

    public static void main(String[] args) {
        Node a5 = new Node(5);
        Node a4 = new Node(4,a5);
        Node a3 = new Node(3,a4);
        Node a2 = new Node(2,a3);
        Node a1 = new Node(1,a2);
//        方式1
         Node rehead = reverse(a1);
//         方式2
//        Node rehead = reverseWithRecursion(n1);
        printList(rehead);
    }
}

转载请标明链接：https://blog.csdn.net/wabiaozia/article/details/106729417