题解 | #反转链表#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode ReverseList (ListNode head) {
    //方法一：双指针（视频解析：bilibili代码随想录）
        // ListNode pre = null;
        // ListNode next = null;
        // while(head != null){
        //     next = head.next;
        //     head.next = pre;
        //     pre = head;
        //     head = next;
        // }
        // return pre;
    //方法二：栈
        // Stack<ListNode> stack = new Stack<>();
        // while(head!=null){
        //     stack.push(head);
        //     head=head.next;
        // }
        // if (stack.isEmpty()){
        //     return null;
        // }
        // ListNode node = stack.pop();
        // ListNode dummy = node;//记录头节点的值
        // while(!stack.isEmpty()){
        //     node.next = stack.pop();
        //     node=node.next;
        // }
        // //最后一个结点就是反转前的头结点，一定要让他的next
        // //等于空，否则会构成环
        // node.next = null;
        // return dummy;
    //方法三：双链表实现
        // ListNode newHead = null;
        // while(head!=null){
        // //首先保存了下一个节点的引用，然后将当前节点的 next 指针指向前一个节点，更新 newHead，最后将 head 移动到下一个节点。
        //     ListNode nextNode = head.next;
        //     head.next = newHead;
        //     newHead = head;
        //     head = nextNode;
        // }
        // return newHead;
        // }
    //方法四：递归，建议根据方法一双指针来写（视频：代码随想录）
        return reverseListInt(head, null);
    }

    private ListNode reverseListInt(ListNode head, ListNode pre) {
        if (head == null)
            return pre;
        ListNode next = head.next;
        head.next = pre;
        return reverseListInt(next, head);
    }
}