剑指offer-反转链表-Java版

写在前面

代码说明：代码的下载地址: https://github.com/WuNianLuoMeng/Coding
视频说明：第一次以这样的形式录视频，如果有哪里说的不对，还请各位及时指出，谢谢~

反转链表 视频链接

方法一：就是通过两个距离为1的移动节点，去不断的去反转原链表相邻的节点之间的指向。

    public ListNode ReverseList(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode frontNode = head;
        ListNode removeNode = head.next;

        while (removeNode != null) {
            ListNode tempNode = removeNode.next; /// 用来保存移动节点的下一个节点，不然的话，就会造成节点最终无法往右移动的情况。
            removeNode.next = frontNode; /// 实现链表的反置
            // 下面两行代码就是实现两个节点的向右平移操作。
            frontNode = removeNode;
            removeNode = tempNode;
        }
        head.next = null;
        return frontNode;
    }

方法二：通过栈去模拟反置的过程（不推荐）

public ListNode ReverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        Stack<ListNode> stack = new Stack<>();
        while (head != null) {
            stack.push(head);
            head = head.next;
        }

        ListNode removeNode = stack.pop(); /// 创建新的链表，需要创建一个新的引用
        ListNode ans = removeNode;
        removeNode.next = null; /// 初始化
        while (!stack.isEmpty()) {
            ListNode x = stack.pop(); /// 取出栈顶节点元素，然后初始化节点元素的next值
            x.next = null;
            /// 可以用链表的尾接法去理解
            removeNode.next = x;
            removeNode = x;
        }
        return ans;

    }