剑指offer最优解Java版-反转链表

题目描述

输入一个链表，反转链表后，输出新链表的表头。

第一种方案：迭代

在head前后设置before和after两个指针，每次反转head指针朝向

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode before = null;
        ListNode after = head.next;
        while (head.next != null) {
            head.next = before;
            before = head;
            head = after;
            after = after.next;
        }
        head.next = before;
        return head;
    }
}

复杂度分析：

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。

第二种方案：递归

利用递归走到链表的末端，然后再更新每一个node的next 值 ，实现链表的反转。而newhead 的值没有发生改变，为该链表的最后一个结点，所以，反转后，我们可以得到新链表的head。

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

class Solution {
    public ListNode ReverseList(ListNode head) {
        // 如果链表为空或者链表中只有一个元素
        if (head == null || head.next == null) {
            return head;
        }
        // 先反转后面的链表，走到链表的末端结点
        ListNode node = ReverseList(head.next);
        // 再将当前节点设置为后面节点的后续节点
        head.next.next = head;
        head.next = null;
        return node;
    }
}

复杂度分析：

• 时间复杂度：O(n)。
• 空间复杂度：O(n)。

哎呀，如果我的名片丢了。微信搜索“全菜工程师小辉”，依然可以找到我