==========================努力奋斗财源广进==========================

一、算法题目

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

二、题解

1、我的题解

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
import java.util.Stack;
public class Solution {
    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 temNode = stack.pop();
            node.next = temNode;
            node = node.next;
        }
        node.next = null;
        return dummy;
    }
}

2、优秀题解

public ListNode ReverseList(ListNode head) {
    //新链表
    ListNode newHead = null;
    while (head != null) {
        //先保存访问的节点的下一个节点，保存起来
        //留着下一步访问的
        ListNode temp = head.next;
        //每次访问的原链表节点都会成为新链表的头结点，
        //其实就是把新链表挂到访问的原链表节点的
        //后面就行了
        head.next = newHead;
        //更新新链表
        newHead = head;
        //重新赋值，继续访问
        head = temp;
    }
    //返回新链表
    return newHead;
}

其实题解的思路很清晰，就是不断的用原来的链表的头节点插入到新链表的头节点。唯一的坏处就是改变了原来的链表结构。

三、解法心得

我的解法相对来说比较简单，就是利用stack来进行一个中间的过渡，比较好的解法是利用双链表的做法。写的比较难懂，绕不过来，我好菜。明天要记得复习下这道算法题目。每天几道题，面试不慌。

四、自我监督

评论区记录复习记录