15 反转链表

题目描述

输入一个链表，反转链表后，输出链表的所有元素。

方法1：
利用循环：
pre head next
1→2→3

 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||head.next==null) return head;
13         ListNode pre = head;
14         head = head.next;
15        _*** pre***__***.next=null;***_
16         while(head!=null){
17             ListNode next= head.next;
18             head.next=pre;
19             pre = head;
20             head = next;
21         }
22         return pre;
23     }
24 }

递归版：

抽象出来

1→2->3

R(2)表示2节点以后的都已经反转好了，而且返回的是反转后的头结点3
1->2←3

我们要做的就是把 1——>2反转成1<——2
1——————>2
pre head

pre.next = null;
head.next = pre;

需要注意把pre.next 置为null

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