链表-Reverse Linked List（反转单向链表）

问题描述：

Reverse a singly linked list.

click to show more hints.

Hint:

A linked list can be reversed either iteratively or recursively. Could you implement both?

思考：

用遍历和递归两种方式实现，使用遍历很好理解，考虑使用三个索引，分别为头head，头后面的一个Next和Next后面的nextNext，head的next为空不说了，关键在每一次访问中的Next的next引用需要变化，但是又是单项链表next变化，后面的节点就找不到了，这就是nextNext的作用。然后是使用递归，参考了别人的例子，用只有两个节点的特殊链表就可以轻松理解。

代码（java）：

1.遍历

public ListNode reverseList(ListNode head) {


if(head == null || head.next == null){
return head;
}


ListNode next;
ListNode nextNext;
next = head.next;
nextNext = next.next;


head.next = null;

while(nextNext!=null){
next.next = head;



head = next;
next = nextNext;
nextNext  = nextNext.next;
}

next.next = head;
head = next;

return head;
}

2.递归

public ListNode reverseList(ListNode head) {
if(head==null) return null;  
if(head.next==null) return head;  

ListNode p = head.next;  
ListNode n = reverseList(p);  

head.next = null;  
p.next = head;  
return n; //递归求法
}