剑指offer-反转链表（递归与非递归）

题目：反转链表

题目描述：输入一个链表，反转链表后，输出链表的所有元素。

思路：

方法一：非递归法

这属于基础题，代码越简洁越好，力求写完一次过。这种题感觉只要在脑海里有个翻转的过程就很容易写出来了，并且保证没有错误

如:1->2->3->4->null

先让1->null

再2->1->null

再3->2->1->null

就这样下去就行

代码：

 1 /*
 2 public class ListNode {
 3     int val;
 4     ListNode next = null;
 5 
 6     ListNode(int val) {
 7         this.val = val;
 8     }
 9 }*/
10 public class Solution {
11     public ListNode ReverseList(ListNode head) {
12         if(head==null)return null;
13         ListNode pre=null;
14         ListNode cur=head;
15         ListNode next=head.next;
16         while(cur!=null){
17             next=cur.next;//保存后面的那个
18             cur.next=pre;//让以前代替后面的
19             pre=cur;     //节点向后移动，一代新人赶旧人，现在成为过去，未来成为现在
20             cur=next;
21         }
22         return pre;
23     }
24 }

方法二：递归法

思路：递归法的思路就死一开始便跑到链表的最后一个节点处，然后从后往前的进行处理

如1->2->3->4->5->null

一系列递归调用后到达链表末尾

          head newhead
1 ->2 ->3 ->4  ->5  ->null

然后

head.next.next = head;//即5现在指向了4
        head.next = null;//4现在指向null

          head     newhead
1 ->2 ->3 ->4->null   5  ->4
即5->4->null

然后便返回上一层递归，在那一层里
head=3,newhead=4
继续重复上面的方法

代码如下：

 1 public class Solution {
 2     public ListNode ReverseList(ListNode head) {
 3         if(head==null||head.next ==null)
 4             return head;
 5         ListNode newhead = ReverseList(head.next);
 6         head.next.next = head;
 7         head.next = null;
 8         return newhead;
 9     }
10  }