反转链表

题目

给定一个单链表的头结点pHead，长度为n，反转该链表后，返回新链表的表头

解题思路

利用栈的先进后出的特点，先将单链表元素依次入栈后在依次弹出生成新的单链表

步骤：

①创建一个栈数据结构

②遍历单链表并将元素push入栈

③将栈顶第一个元素pop出栈并作为新链表表头

④将栈中的元素依次pop出栈并生成新的单链表

注意：

栈底的最后一个元素作为单链表的尾节点，并且需要将next指向置空，否则会造成无限循环，因为这个元素来自于反转前的单链表表头next指向另一个节点的

示例代码

/**
	public class ListNode {
    	int val;
    	ListNode next = null;
    	ListNode(int val) {
    	   	this.val = val;
		}
	}
*/
    
public class Solution{
	public static void reverseListNode(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 result = node;
        while(!stack.isEmpty()){
            ListNode tempNode = stack.pop();
            node.next = tempNode;
            node = node.next;
        }
        // 链表尾部节点next指向置空，防止死循环
        node.next = null;
        return result;
    }
}

题目链接：

https://www.nowcoder.com/exam/oj?page=1&tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295