[数据结构与算法]剑指 Offer 10（链表篇2）.反转链表

剑指 Offer 10（链表篇2）.反转链表

问题描述：

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

解题思路：

了解链表本身的性质，学会利用递归和栈的思想，具体详情见代码注释。

示例：

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

利用迭代的方法实现链表反转

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { 
 *        val = x; 
 *     }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        //引用ListNode类创建一个新的结点node，里面存储元素为空
        ListNode node = null;
        //当链表中存储的元素不为空时
        while(head != null){
            //创建一个现在的结点为头结点的下一个结点
            ListNode cur = head.next;
            //让头结点的下一个结点传递到node结点
            head.next = node;
            //使node结点为头结点，开始对链表里的元素进行反转
            node = head;
            head = cur;
        }
        //更新node结点
        return node;
    }
}

利用递归的方法实现链表反转

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { 
 *        val = x; 
 *     }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        //如果头结点和头结点的下一个结点为空，不用考虑反转，直接返回头结点即可
        if(head == null || head.next == null){
            return head;
        }
        //递归调用head.next相当于遍历了所有结点
        ListNode node = reverseList(head.next);
        //设定原现结点cur为head.next
        ListNode cur = head.next;
        //由于反转需要将现结点cur的下一个结点指向head头结点
        cur.next = head;
        //根据题目要求头结点指向空
        head.next = null;
        return node;
    }    
}

利用栈实现链表反转

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { 
 *        val = x; 
 *     }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        //如果头结点为空，不用考虑反转，直接返回头结点即可
        if(head == null){
            return head;
        }
        //建立一个栈利用栈的思想将元素反转
        Stack<ListNode> stack = new Stack<>();
        //当头结点不为空时
        while(head != null){ 
            //从头结点开始依次放入链表元素
            stack.push(head);
            head = head.next;
           
        }
        //由于链表输出需要头结点，原有的头结点已经不能使用，将第一个弹出栈的元素即为原头结点建立为新个头节点
        ListNode newHead = stack.pop();
        ListNode newNode = newHead;
        while(!stack.isEmpty()){
            ListNode cur = stack.pop();
            //头结点的下一个结点为为栈中弹出的第二个元素
            newNode.next = cur;
            //改变头结点的位置
            newNode = cur;
        }
        //根据市里要求，最后结果输出为null
        newNode.next = null;
        return newHead;
    }    
}