Leetcode:206.反转链表

题目描述

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

思路1:迭代

使用三个指针分别指向之前，现在和将来的位置，然后遍历逆转即可

思路2:递归

需要考虑从尾指针开始，然后开始递归，即考虑从后开始。然后利用当前指针的下一个位置进行递归，然后逆转。

代码

代码1

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

        while(now != null){
            now.next = pre;
            pre = now;
            now = forward;
            if (forward != null){
                forward = forward.next;
            }
        }
        return pre;
    }
}

代码2

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

复杂度分析

思路1时间复杂度

$O(n)$

思路1空间复杂度

$O(1)$

思路2时间复杂度

$O(n)$

思路2空间复杂度

$O(n)$会使用n层栈空间