力扣 - 剑指 Offer 24. 反转链表

题目

剑指 Offer 24. 反转链表

思路1（迭代）

• 使用一个指针pre指向上一个节点，初始值为null，然后遍历链表，一边遍历一遍交换指针指向：
  1. 先用nextNode下下一个节点
  2. 然后将cur指向pre
  3. 之后将pre指向cur
  4. 最后将cur指向nextNode即可完成两个节点的反转
  5. 我们遍历整个链表，对所有的节点都这样做，那么也就完成了整个链表的反转

代码

class Solution {
    public ListNode reverseList(ListNode head) {
        // 保证链表的元素大于1个时才反转
        if (head == null || head.next == null) {
            return head;
        }

        // 常见pre指针，存储上一个节点，要指向null，因为要保证第一个元素的next能指向null
        // 反转过程是这样的：首先存储当前节点的下一个节点nextNode，然后将当前元素的next指向pre，最后将pre指向head、head指向nextNode即可
        ListNode pre = null;
        while (head != null) {
            ListNode nextNode = head.next;
            head.next = pre;
            pre = head;
            head = nextNode;
        }

        // 此时head指向的是null，pre指向的是反转后的头节点
        return pre;
    }
}

复杂度分析

• 时间复杂度：\(O(N)\)
• 空间复杂度：\(O(1)\)

思路2（递归）

• 递归方式理解起来稍微比迭代绕一点
• 首先是要递归链表，遇到链表末尾的话结束递归，此时拿到的末尾节点也就是反转后的头节点，所以我们在每一层递归将这个节点传递返回
• 当递归到链表末尾的时候，我们才从链表末尾开始修改指针指向：将当前节点的下一个节点的next指针指向当前节点，即cur.next.next = cur，然后将当前节点cur的指针指向null(如果不指向null的话会导致反转后的最后一个节点不是指向null，因此形成环)，每一层递归都这样子做，最后就可以将链表反转了
• 注意：
  1. 返回的值是最后一个节点
  2. 同时要将cur的next指向null

代码

class Solution {
    public ListNode reverseList(ListNode head) {
        // 只有链表节点个数大于1个时候才需要反转
        if (head == null || head.next == null) {
            return head;
        }
        // 反转链表
        return dfs(head);
    }

    public ListNode dfs(ListNode node) {
        // 遍历到最后一个节点的时候开始返回
        if (node.next == null) {
            return node;
        }

        // 获取链表的最后一个节点，也是将来的反转之后的头节点
        ListNode last = dfs(node.next);

        // 进行链表指针的指向的修改
        // 将下一个节点的next指向当前节点
        node.next.next = node;
        // 将当前节点指向null
        // 如果这个不设置null的话，最后一个节点就不能指向null了，导致存在环形链表
        node.next = null;
        
        return last;
    }
}

复杂度分析

• 时间复杂度：\(O(N)\)
• 空间复杂度：\(O(N)\)，递归所需要的栈空间