算法题-简单系列-01-链表反转

1. 题目

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
如当输入链表{1,2,3}时，
经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
以上转换过程如下图所示：

示例1
输入：{1,2,3}
返回值：{3,2,1}

示例2
输入：{}
返回值：{}

说明：
空链表则输出空

1.1 使用栈解决

 /**
     * 链表反转的第一种方式，通过栈的先进后出
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode ReverseList (ListNode head) {
        // write code here
        //思路: 利用栈的数据结构，先进后出，先将链表的数据放到栈里面，然后再取出来，形成链表
        Stack<ListNode> stack = new Stack<>();
        while (head != null) {
            stack.push(head);
            head = head.next;
        }
        if (stack.empty()) {
            return null;
        }
        ListNode firstNode = stack.pop();
        //让需要返回的节点指针永远指向第一个节点的引用
        ListNode result = firstNode;
        //取出栈里面剩余的节点,依次加入链表
        while (!stack.empty()) {
            ListNode nextNode = stack.pop();
            //将取出的下一个节点 挂在上一个节点的下面
            firstNode.next = nextNode;
            //移动指针引用
            firstNode = firstNode.next;
        }
        //栈里面的数据取完之后,将节点的最后的引用置为null
        firstNode.next = null;
        return result;
    }

1.2 反转链表

    /**
     * 链表反转的第二种方式，通过改变指针的引用
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode ReverseList (ListNode head) {
        // write code here
        // 从原来的节点之上循环摘下一个节点，将指针逆向链接即可
        if (head == null) {
            return null;
        }
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null) {
            //将下一个节点临时存起来
            ListNode next = cur.next;
            //将指针逆向指
            cur.next = prev;
            //将cur赋值给pre
            prev = cur;
            //继续赋值
            cur = next;
        }
        return prev;
    }