Java数据结构与算法（剑指offer）——输入一个链表，反转链表后，输出新链表的表头。

链表的定义。 public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }

代码实现

方法1： 主要思路：

先定义一个节点遍历原来的节点，每遍历到一个一个节点，就将其放在新节点的最前端 import java.util.*; public class Solution { public ListNode ReverseList(ListNode head) { // 方法一： ListNode newNode = null;//这里设置为空时，可以 ListNode cur=head; ListNode pre=null; while(cur!=null){ pre=cur.next;//用于保存当前节点的下一个节点 cur.next=newNode;//cur的下一个节点指向新的链表的最前端 newNode=cur;//将cur 连接到新的链表上 cur=pre; } return newNode; } }

方法2：利用栈。主要思路：将原始给定的链表先遍历，压入s1中，再将s1依次出栈，存放到新的ListNode中。

//方法二, Stack<ListNode> s1= new Stack(); ListNode node=new ListNode(0); ListNode cur =head; while(cur!=null){ s1.push(cur);//入栈 cur=cur.next; } while(s1.size()>0){ node.next=s1.pop();//出栈，赋值给新节点 node=node.next; } return node.next;