链表结构
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来改变指针，使最后一个节点依次指向第一个节点。
