# 206.Reverse Linked List (E)

## 1.Decription(Easy)

Reverse a linked list.

**Example**

For linked list`1->2->3`, the reversed linked list is`3->2->1`

## 2.Code

**Version 1: Non-recursive:**

经典reverse linked list

```
 public ListNode reverse(ListNode head) {
       if(head==null || head.next==null){
              return head;
          }

          ListNode prev=null;
          ListNode curt=head;

          while(curt!=null){
              ListNode post=curt.next;
              curt.next=prev;
              prev=curt;
              curt=post;                        
          }

          return  prev;
    }
```

**Version 2: Recursive**

递归反转单链表的算法可能很多读者都听说过，这里详细介绍一下，直接看代码实现：

```java
ListNode reverse(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode last = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return last;
}
```

看起来是不是感觉不知所云，完全不能理解这样为什么能够反转链表？这就对了，这个算法常常拿来显示递归的巧妙和优美，我们下面来详细解释一下这段代码。

**对于递归算法，最重要的就是明确递归函数的定义**。具体来说，我们的 `reverse` 函数定义是这样的：

**输入一个节点 `head`，将「以 `head` 为起点」的链表反转，并返回反转之后的头结点**。

明白了函数的定义，再来看这个问题。比如说我们想反转这个链表：

[![](https://labuladong.github.io/algo/images/%E5%8F%8D%E8%BD%AC%E9%93%BE%E8%A1%A8/1.jpg)](https://labuladong.github.io/algo/images/%E5%8F%8D%E8%BD%AC%E9%93%BE%E8%A1%A8/1.jpg)

那么输入 `reverse(head)` 后，会在这里进行递归：

```java
ListNode last = reverse(head.next);
```

不要跳进递归（你的脑袋能压几个栈呀？），而是要根据刚才的函数定义，来弄清楚这段代码会产生什么结果：

[![](https://labuladong.github.io/algo/images/%E5%8F%8D%E8%BD%AC%E9%93%BE%E8%A1%A8/2.jpg)](https://labuladong.github.io/algo/images/%E5%8F%8D%E8%BD%AC%E9%93%BE%E8%A1%A8/2.jpg)

这个 `reverse(head.next)` 执行完成后，整个链表就成了这样：

[![](https://labuladong.github.io/algo/images/%E5%8F%8D%E8%BD%AC%E9%93%BE%E8%A1%A8/3.jpg)](https://labuladong.github.io/algo/images/%E5%8F%8D%E8%BD%AC%E9%93%BE%E8%A1%A8/3.jpg)

并且根据函数定义，`reverse` 函数会返回反转之后的头结点，我们用变量 `last` 接收了。

现在再来看下面的代码：

```java
head.next.next = head;
```

[![](https://labuladong.github.io/algo/images/%E5%8F%8D%E8%BD%AC%E9%93%BE%E8%A1%A8/4.jpg)](https://labuladong.github.io/algo/images/%E5%8F%8D%E8%BD%AC%E9%93%BE%E8%A1%A8/4.jpg)

接下来：

```java
head.next = null;
return last;
```

[![](https://labuladong.github.io/algo/images/%E5%8F%8D%E8%BD%AC%E9%93%BE%E8%A1%A8/5.jpg)](https://labuladong.github.io/algo/images/%E5%8F%8D%E8%BD%AC%E9%93%BE%E8%A1%A8/5.jpg)

神不神奇，这样整个链表就反转过来了！递归代码就是这么简洁优雅，不过其中有两个地方需要注意：

1、递归函数要有 base case，也就是这句：

```java
if (head.next == null) return head;
```

意思是如果链表只有一个节点的时候反转也是它自己，直接返回即可。

2、当链表递归反转之后，新的头结点是 `last`，而之前的 `head` 变成了最后一个节点，别忘了链表的末尾要指向 null：

```java
head.next = null;
```

理解了这两点后，我们就可以进一步深入了，接下来的问题其实都是在这个算法上的扩展。