11链表-迭代与递归

目录

LeetCode之路——206. 反转链表

分析：

解法一：迭代

解法二：递归

---

LeetCode之路——206. 反转链表

给你单链表的头节点 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

分析：

解法一：迭代

重复某一过程，每一次处理结果作为下一次处理的初始值，这些初始值类似于状态，每次处理都会改变状态，直到到达最终状态。

从前往后遍历链表时，将当前节点的next指针改为指向前一个节点，因此需要一个变量存储上一个节点prev，当前节点处理完需要找下一个节点，所以需要一个变量保存当前节点curr，处理完需要将当前节点赋值给prev，并将next指针赋值给curr，因此需要一个变量提前保存下一个节点的指针next。

1. 定义变量对应prev，curr，next。

2. 将当前节点存入curr变量 curr=head.

3. 将下个节点指针保存到next = curr.next.

4. 变换指针 curr.next = prev;

5. 开始下一次迭代 prev = curr; curr=next;

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

• 时间复杂度：O(n)

• 空间复杂度：O(1)

解法二：递归

以相似的方法重复，类似于树结构，先从根节点找到叶子节点，从叶子节点开始遍历，大的问题（链表反转）拆解为性质相同的小问题（两个元素反转）。

1. 从节点1和2开始拆解两元素反转发现链表断了。

2. 所以从末尾开始拆解。

3. 单次反转默认为A和B节点，head.next.next = head;head.next = null;

4. 递归的边界条件就是head == null || head.next == null。

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)

• 空间复杂度：O(n)