题目描述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

image-20210508164052248

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

补充

ListNode定义如下

public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }

解法

我之前刚好看过这个题的解析教程，所以就用递归小小的装个逼

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

        ListNode last = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }

大概思路如下：

这个递归其实做的是：

​ 如果这和链表是个空的或者只有一个节点，则反转之后还是本身。

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

​ 如果不是，则一直查找下一个节点，

ListNode last = reverseList(head.next);

​ 直到某个节点的next的next为null【其实就是找倒数第二个节点】

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

并将last=最后一个节点

ListNode last = reverseList(head.next);
image-20210508170111643

此时head=倒数第二个节点

image-20210508170602536

在将此时head的next的next指向head，【其实就是把最后一个节点指向倒数第二个，做的就是反转链表】

head.next.next = head;
image-20210508170948257

这时候 将head.next=null 【把head指向空】

head.next = null;
image-20210508171244794

这时候，其实已经反转了一部分了。

然后再将last返回给上一级【也就是3】，此时last=最后一个节点【也就是5】。

其他的节点 以此类推，直到结束

最后的时候，再返回一个last，也就是5

image-20210508183826788

结束