反转单链表

一、题目。

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

示例 1：

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

输入：head = [1,2]
输出：[2,1]
示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

二、代码。

• 双指针

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode pre=null;
        while(head!=null){
            ListNode next=head.next;
            head.next=pre;
            pre=head;
            head=next;
            
        }
        return pre;
       
         

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

双指针思路简单不解释

复杂度分析

时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次。

空间复杂度：O(1)。

• 递归

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

思路：
递归自己的理解是一件事情中途需要干另一件事情，另一件事情的中途还需要干另一件，直到满足退出的条件，干完了最后一件事情去回头又干前一件没干完的事情，直到干完最初的一件事情。类似于嵌套。
此题递归的最后一步是找到了最后一个节点，return的head指向的是最后一个节点。所以neww是最后一个节点。所以就开始做倒数第二件事情，此时的head是倒数第二个节点，head.next是最后一个节点，将其的next指向倒数第二个，就实现了最后两个节点的置逆，再把head的next指向null。依次置逆，就实现了全部的置逆。

复杂度分析

时间复杂度：O(n)，其中 n是链表的长度。需要对链表的每个节点进行反转操作。

空间复杂度：O(n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 n 层。