题解 | #反转链表#

思路
1.递归，这道题没办法使用递归，因为没有链，只有节点，无法正确返回头节点
2.双指针，很简单。pre指针与current指针，通过一个辅助指针就可以实现挪动一步就反转一个节点
3.入栈法，也挺简单。

结果
1.双指针法
运行时间：15ms
占用内存：11012KB

2.入栈法
运行时间：15ms
占用内存：10964KB

代码
1.双指针

public class Solution {
    public ListNode ReverseList(ListNode head) {
        // 方法2-双指针法
        ListNode preNodePoint = null;
        ListNode currentNodePoint = head;

        while (currentNodePoint != null){
            ListNode tempNext = currentNodePoint.next;

            currentNodePoint.next = preNodePoint;

            preNodePoint = currentNodePoint;

            currentNodePoint = tempNext;
        }
        return preNodePoint;
    }
}

1.入栈法

import java.util.Stack;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/


public class Solution {
    // 栈法
    public ListNode ReverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        Stack<ListNode> stack = new Stack<>();
        while (head != null){
            stack.push(head);
            head = head.next;
        }

        ListNode newHeadNode = stack.peek();
        while (!stack.isEmpty()){
            ListNode lastNode = stack.pop();
            if (stack.isEmpty()) lastNode.next = null;
            else lastNode.next = stack.peek();
        }

        return newHeadNode;
    }
}