题目描述
输入一个链表，反转链表后，输出链表的所有元素。
输入描述
链表
输出描述
反转链表
题目分析
节点申明：
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
这里的头结点也有val值，它不是一个空节点。
解法一（递归） 运行时间：31ms 占用内存：688k
public class Solution {
public ListNode ReverseList(ListNode head) {
if(head==null || head.next==null){
return head;
}
ListNode p=head.next;
ListNode newHead=ReverseList(p);
p.next = head;
head.next =null;
return newHead;
}
}
把整个链表看成只有两个节点（头结点和剩下的节点），反转只用 剩下的节点 的尾指针指向头结点，头结点的指针指向空。再把 剩下的节点 看成两个节点，依次递归即可。
解法二 运行时间：32ms 占用内存：629k
import java.util.*;
public class Solution {
public ListNode ReverseList(ListNode head) {
if(head==null || head.next==null){
return head;
}
Stack stack = new Stack();
ListNode in = head;
ListNode out = head;
while(in!=null){
stack.push(in.val);
in = in.next;
}
while(out!=null){
out.val = (int)stack.pop();
out = out.next;
}
return head;
}
}
链表的结构和指针不变，把整个链表的值（val）反转存入即可（利用Stack存值）。
解法三 运行时间：29ms 占用内存：629k
import java.util.*;
public class Solution {
public ListNode ReverseList(ListNode head) {
if(head==null || head.next==null){
return head;
}
ListNode cur=head;
ListNode pre=null;
ListNode next=null;
while(cur!=null)
{
next=cur.next;
cur.next=pre;
pre=cur;
cur=next;
}
return pre;
}
}
链表的值不变，利用中转节点pre来改变指针，使最后一个节点依次指向第一个节点。
