剑指 Offer 24. 反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

限制：

0 <= 节点个数 <= 5000

解题方法一

 /**
     * 借助辅助空间
     * 效率低
     * @param head
     */
    private static ListNode reverseList0(ListNode head) {
        List<Integer> arr = new ArrayList<>();
        while (head != null) {
            arr.add(head.val);
            head = head.next;
        }
        ListNode newHead = new ListNode(arr.get(arr.size() - 1));
        for (int i = arr.size() - 2; i >= 0; i--) {
            ListNode node = new ListNode(arr.get(i));
            newHead.next = node;
            newHead = node;
        }
        return newHead;
    }
    private static ListNode reverseList1(ListNode head) {
        if (head == null) {
            return null;
        }
        ArrayList<ListNode> nodeList = new ArrayList<>();
        while (head != null) {
            nodeList.add(head);
            head = head.next;
        }
        int startIndex = nodeList.size() - 1;
        for (int i = startIndex; i >= 0; i--) {
            ListNode node = nodeList.get(i);
            if (i == 0) {
                node.next = null;
            } else {
                node.next = nodeList.get(i - 1);
            }
        }
        //现在头结点是原来的尾节点
        head = nodeList.get(startIndex);
        return head;
    }

解题方法二

 /**
     * 使用指针迭代遍历
     * 时间复杂度 O(N) ： 遍历链表使用线性大小时间。
     * 空间复杂度 O(1) ： 变量 pre 和 cur 使用常数大小额外空间。
     * @param head
     * @return
     */
    private ListNode reverseList(ListNode head) {
        if (head == null){
            return null;
        }
        ListNode prev = null;  // 当前指针的前一个
        ListNode curr = head;  //当前指针 初始化为头节点
        // 当当前指针走到最后结束
        while (curr != null){
            ListNode temp = curr.next;  //临时节点 指向当前指针的下一个  用于保存链表的地址
            curr.next = prev;  // 将当前指针指向前一个
            // 为下一次循环准备
            prev = curr;  // 向后移动指针
            curr = temp;  // 向后移动指针
        }
        return prev; //当当前指针指向null停止循环后 他的前一个指针就是需要返回的头节点
    }

解题方法三

/**
     * 使用递归法遍历链表
     * 时间复杂度 O(N) ： 遍历链表使用线性大小时间。
     * 空间复杂度 O(N) ： 遍历链表的递归深度达到 N ，系统使用 O(N) 大小额外空间。
     *
     * 使用递归法遍历链表，当越过尾节点后终止递归，在回溯时修改各节点的 next 引用指向。
     *
     * recur(cur, pre) 递归函数：
     * 终止条件：当 cur 为空，则返回尾节点 pre （即反转链表的头节点）；
     * 递归后继节点，记录返回值（即反转链表的头节点）为 res ；
     * 修改当前节点 cur 引用指向前驱节点 pre ；
     * 返回反转链表的头节点 res ；
     * reverseList(head) 函数：
     * 调用并返回 recur(head, null) 。传入 null 是因为反转链表后， head 节点指向 null ；
     *
     * @param head
     * @return
     */
    private ListNode reverseLis2(ListNode head) {
        return recur(head, null);    // 调用递归并返回
    }
    private ListNode recur(ListNode cur, ListNode pre) {
        if (cur == null) return pre; // 终止条件
        ListNode res = recur(cur.next, cur);  // 递归后继节点
        cur.next = pre;              // 修改节点引用指向
        return res;                  // 返回反转链表的头节点
    }

微信关注

WeChat