描述

反转链表

思路1：使用栈存储

使用栈存储每个节点，再pop取出节点，构造新链表。（也可以用列表，倒序取出，i--）

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null) {
            return null;
        }
        Stack<ListNode> stack = new Stack<>();
        ListNode p = head;
        while(p != null) {
            stack.push(p);
            p = p.next;
        }
        ListNode ret = stack.pop();
        p = ret;
        while(!stack.isEmpty()) {
            p.next = stack.pop();
            p = p.next;
        }
        //最后一个节点是原链表的头节点，next是第二个节点，需要断开，否则会构成环
        p.next = null;
        return ret;
    }
}

思路2：三指针

三指针：前一个节点、当前节点、下一个节点

public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode tmp;
        while(cur != null) {
            //保存下一个节点
            tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}

思路3：递归

递归回弹时（出栈时）处理

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode node = ReverseList(head.next);
        head.next.next = head;  //尾节点指向倒数第二个节点
        head.next = null;   //指向null
        return node;
    }
}

思路4：递归

递归：f(n,n-1)=f(n+1,n)+n指向n-1

[1,null], [2,1], [3,2], [null,3]（终止）, [3,2], [2,1], [1,null]

public class Solution {
    public ListNode ReverseList(ListNode head) {
        return recur(head, null);
    }
    private ListNode recur(ListNode cur, ListNode pre) {
        if (cur == null) {
            return pre;
        }
        // 递归后继节点
        ListNode res = recur(cur.next, cur);
        // 修改节点引用指向
        cur.next = pre;
        // 返回反转链表的头节点
        return res;
    }
}

思路5：尾递归

类似于三指针

public class Solution {
    public ListNode ReverseList(ListNode head) {
        return recur(head, null);
    }
    private ListNode recur(ListNode cur, ListNode newHead) {
        if (cur == null) {
            return newHead;
        }
        //保存下一个节点
        ListNode next = cur.next;
        //断开原链表，指向新链表
        cur.next = newHead;
        return recur(next, cur);
    }
}

思路5：倒着构造链表

倒着构造链表，保存已构造好的链表，每次循环创建新的头节点，连接上已构造好的链表

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null) {
            return null;
        }
        ListNode ret = new ListNode(head.val);
        while(head.next != null) {
            ListNode newHead = new ListNode(head.next.val);
            newHead.next = ret;
            ret = newHead;
            head = head.next;
        }
        return ret;
    }
}