《剑指offer》 第24题 翻转链表

题目描述
输入一个链表，反转链表后，输出新链表的表头。

思路1：最开始的思路是使用栈

import java.util.Stack;
public class Solution {
    public ListNode ReverseList(ListNode head) {
    if(head == null) return null;
    Stack<ListNode> stack=new Stack<ListNode>();
    while (head!=null){
        stack.push(head);
        head=head.next;
    }  
    head = stack.pop();  //从栈再倒给链表
    ListNode res = head; //先记录首个节点，再倒。如果本题不返回首个元素，可以直接倒
    while (!stack.isEmpty()){
        head.next = stack.pop();
        head = head.next;
    }
        head.next = null;
    return res;
    }
}

思路2：由于栈的使用需要额外的空间，第二个想法就是交换指针，让A指向B变成B指向A
其他大佬的图解和描述很详细。
A->B->C->null 变成 null<-A<-B<-C

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if (head == null || head.next==null) return head;
     //初始情况head指向A
        ListNode pre = null;// 当前节点的前一个节点 也就是A翻转后要指向null
        ListNode post = head;// 当前节点的下一个节点  这里先指向A
        while(head!=null)
        {
            post = head.next;// 记录当前节点的下一个节点位置  下一位置是B，所以指B
            head.next = pre;// 让当前节点指向前一个节点位置，这一步完成由A指B变B指A
            pre = head;// pre 往右走， pre指向A，也就是B翻转后要指向A。B的前一节点
            head = post;// 当前节点往右继续走  此时head由A变B,意味着完成一次翻转。
//初始是pre是null，head是A,post是A，此时pre是A，head是B,post是B。完成了A的反转
        }
        return pre;
    }
}

思路3：递归 （暂时没理解透彻）

public class Solution {
    public ListNode ReverseList(ListNode head) {
     if(head==null||head.next ==null)
            return head;
        ListNode next = head.next;
        ListNode prev = ReverseList(next);
        head.next.next = head;
        head.next = null;
        return prev;
    }
}