链表反转 原地反转、头插法、递归 LeetCode 206 剑指offer 24 Java实现

    //双指针法(原地反转)
    public ListNode reverseList1(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode pre = null, cur = head, next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    //头插法
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode();
        while (head != null) {
            ListNode next = head.next;
            head.next = dummy.next;
            dummy.next = head;
            head = next;
        }
        return dummy.next;
    }

    //递归法
    public ListNode reverseList3(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead =  reverseList(head.next);
        head.next.next = head;
        //这一句实际上执行一次就够了,
        head.next = null;
        return  newHead;
    }

    //递归法优化
    public ListNode reverseList4(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = helper(head);
        head.next = null;
        return newHead;
    }

    public ListNode helper(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = helper(head.next);
        head.next.next = head;
        return newHead;
    }

发表评论

电子邮件地址不会被公开。 必填项已用*标注