24.反转链表

剑指 Offer II 024. 反转链表

题目：
给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。

示例.png

迭代法，利用前驱结点一个一个反转next指向，每反转一个就更新前驱结点和当前结点到下一个位置
时间复杂度:O(n) 空间复杂度:O(1)

class Solution {

    public ListNode reverseList(ListNode head) {
        
        //0.边界处理
        if(head==null) return null;

        //1.定义需要的数据结构
        ListNode prev = null;
        ListNode curr = head;

        //2.循环反转链表
        while(curr != null) {
            ListNode tmp = curr.next;
            curr.next = prev;//改变指针指向
            //更新前驱结点和当前结点
            prev = curr;
            curr = tmp;
        }

        //3.返回结果
        return prev;

    }
 

递归 时间复杂度:O(n) 空间复杂度:O(n)

    public ListNode reverseList1(ListNode head) {
        return reverse(null,head);
    }

    private ListNode reverse(ListNode prev,ListNode curr){
       
       //递归退出条件
       if(curr==null) {
           return prev;
       }

       //保存当前结点的下一个结点
       ListNode next = curr.next;
       //设当前结点的下一个结点为当前结点的前驱结点
       curr.next = prev;

       //递归 反转当前结点和下一个结点
       return reverse(curr,next);
    }

}

执行结果.png