【力扣】反转链表

反转链表

给定单链表的头结点head，反转链表，并返回反转后的链表。

示例1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

1.双链表求解

双链表求解就是把原链表的结点一个一个摘掉，每次摘掉的链表都让他成为新的链表的头结点，然后更新链表。
以1–>2–>3–>4 为例：

class Solution {
    public ListNode reverseList(ListNode head) {
        //新链表
        ListNode newHead = null;
        while (head != null) {//遍历原链表
            //保存访问的节点的下一个节点
            ListNode temp = head.next;
            //每次访问的原链表节点都会成为新链表的头结点，
            //把新链表挂到访问节点的后面
            head.next = newHead;
            //更新新链表
            newHead = head;

            //重新赋值，往后继续访问
            head = temp;//当前访问节点的下一个节点
        }
        //返回新链表
        return newHead;
    }
}

2.使用栈解决

原理：把链表节点一个个入栈，当全部入栈完之后再一个个出栈，出栈的时候在把出栈的结点串成一个新的链表。

public ListNode reverseList(ListNode head) {
    Stack<ListNode> stack = new Stack<>();//创建栈
    //把链表节点全部摘掉放到栈中
    while (head != null) {
        stack.push(head);//入栈
        head = head.next;
    }
    if (stack.isEmpty())
        return null;
        
    ListNode node = stack.pop();//将栈顶元素取出作为头结点
    ListNode dummy = node;//创建新链表
    //栈中的结点全部出栈，然后重新连成一个新的链表
    while (!stack.isEmpty()) {
        ListNode tempNode = stack.pop();
        node.next = tempNode;
        node = node.next;
    }
    //最后一个结点就是反转前的头结点，一定要让他的next等于空，否则会构成环
    node.next = null;
    return dummy;
}