[数据结构与算法]【leetcode刷题】206. 反转链表

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

实例一：

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

输出：[5,4,3,2,1]

?实例二：

输入：head = [1,2]

输出：[2,1]

实例三：

输入：head =?[ ]

输出：[ ]

提示：

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

思路一：

我们可以从前往后依次遍历链表，用三个指针来分别指向当前结点cur，前驱结点prev，后继结点curNext，然后将当前节点的next指向prev

注意：如果没有curNext的话，那么在修改了cur.next之后cur的后面的结点直接就找不到了

中间过程如下图：

?代码

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) {      // 空链表直接返回
            return head;       
        }                       
        ListNode prev = null;
        ListNode cur = head;
        ListNode next;
        while (cur != null) {
            next = cur.next;       
            cur.next = prev;
            prev = cur;
            cur = next;       
        }
        return prev;     // 循环结束之后prev指向原链表的最后一个结点，也就是新链表的第一个节点
    }
}

复杂度分析

时间复杂度：O(N)? 遍历链表, N 为链表长度

空间复杂度：O(1)

思路二：

递归

在递的过程中走到链表的最后一个结点，递归约束条件便是遍历整个链表的结束条件，在归的过程中完成next的指向修改

代码：

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

复杂度分析

时间复杂度：O(N), N 为链表长度，对每个结点都要进行一次next的修改操作

空间复杂度：O(N), N 为链表长度，递归复杂度主要取决于递归压栈占用的栈空间