反转链表的两种迭代解法和一种递归解法(Java)

原题链接
最常考的链表题型

迭代法本质都类似，都用指针保留了结点信息。都使用了3个指针，这是因为在改变next域后，原结点的后继位置将丢失。

• 迭代解答1遍历法（时间O(n) 空间O（1））

class Solution {
    public ListNode reverseList(ListNode head) {
        //定义三个指针 prev cur curNext 其中cur是用于反转的结点 prev是cur的前驱 
        //但cur的next的指向改变后 原cur的后继的位置会丢失 所以采用了curNext记录cur的位置
        ListNode cur = head;
        ListNode prev = null;
        ListNode curNext = null;
        while (cur != null) {
            curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return prev;
    }
}

• 迭代解法2 头插法（时间O(n) 空间O（1））

class Solution {
    public ListNode reverseList(ListNode head) {
        //头插法只需两个临时指针 相对容易理解
        //cur是当前要反转的结点 curNext存储cur的后继
        //每次先存储curNext   再让cur的next域指向head（头插） cur赋给head curNext赋给cur 
        if (head == null) return null; //头插法必须保证head结点不是空
        ListNode cur = head.next;
        head.next = null;//防止链表出现环
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }
}

递归相对迭代更难理解

• 进阶递归解法（时间O(n) 空间O（n））

class Solution {
    public ListNode reverseList(ListNode head) {
        //递归反转单链表 思路是:把问题化成性质相同的子问题 反转一个链表 等于反转以头结点的next为头的链表(如果不为null)
        //在把头结点的next结点指向头
        if (head == null || head.next == null) return head;
        ListNode ret = reverseList(head.next);//所有的反转链表都拥有用一个尾 所以采用了返回值传递的方式
        head.next.next = head;
        head.next = null;
        return ret;
    }
}