How to determine the time complexity of a recursive function that has a loop enclosed in it?

Question

I am trying to solve LeetCode problem 143. Reorder List:

You are given the head of a singly linked-list. The list can be represented as:

L₀ → L₁ → … → L_{n − 1} → L_n

Reorder the list to be on the following form:

L₀ → L_n → L₁ → L_{n − 1} → L₂ → L_{n − 2} → …

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

This is my attempt at it:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return; 
        }

        ListNode n1 = head;
        ListNode temp = null;

        while (n1.next.next != null) {
            n1 = n1.next;
        }

        temp = n1.next;
        n1.next = null;
        temp.next = head.next;
        head.next = temp;

        reorderList(temp.next);
    }
}

I'm unable to come up with concrete reasoning for the time complexity of my code. My brain says O(n^2) but I just can't justify the why. How can the time complexity be derived?

Answer 1

my brain says O(n^2) but i just can't justify the why.

Yes, it is O(²). One execution of reorderList -- excluding the recursive call -- will visit all the nodes in the list in the while loop. So if at that moment there are nodes in the list, this will be O(). The recursive call is made with a list that has −2 elements (since head and temp are "behind" the reference that is passed to the recursive call). This means we have a number of visits that progresses as follows:

+ −2 + −4 + ... + (1 or 2)

This is about the double of the /2 triangular number, which is O(/2(/2+1)) = O(²).

Improving the time complexity

It is possible to solve this problem with O() time complexity. Here are some spoiler hints to get an idea how to approach it:

Hint 1:

Could you manipulate the list so that it becomes easier to also traverse the list from its current last node backwards?

Hint 2:

What is the time complexity to reverse a linked list?

Hint 3:

Would it help to split the list into two lists?

Spoiler O() solution:

class Solution { public ListNode getMiddle(ListNode head) { ListNode fast = head.next; while (fast != null && fast.next != null) { head = head.next; fast = fast.next.next; } return head; } public ListNode splitAfter(ListNode newTail) { ListNode head = newTail.next; newTail.next = null; return head; } public ListNode reverse(ListNode head) { ListNode prev = null; while (head != null) { ListNode next = head.next; head.next = prev; prev = head; head = next; } return prev; } public void zip(ListNode head1, ListNode head2) { if (head1 == null) return; ListNode head = head1; ListNode tail = head1; while (head1 != null && head2 != null) { head1 = head1.next; tail = tail.next = head2; head2 = head2.next; tail = tail.next = head1; } } public void reorderList(ListNode head) { if (head != null) { zip(head, reverse(splitAfter(getMiddle(head)))); } } }