Something wrong in reversing a linked list recursively

Question

I'm trying to solve a code challenge that asks to reverse a linked list. Given is a pointer to the head node.

Here is my attempt:

struct ListNode* reverseList(struct ListNode* head) {
    if(head==NULL || head->next==NULL) return head;
    struct ListNode* p=reverseList(head->next);
    p->next=head;
    return head;
}

When I dry run, it seems to work fine. But when I submit the code to be tested, a time-limit exceeded (TLE) error occurs.

Why is this happening? What am I doing wrong?

Answer 1

There are two distinct problems with your reverse function:

• It will introduce a cycle in the linked list when it has more than one node. This means that if there is code that doesn't expect a cycle, and just naively iterates through all nodes of the resulting list, it will get into an infinite loop. This could explain the time limit error you get.

• It returns the original head of the list. Instead, it should return the tail of the original list, as that will be the first node of the reversed list.

Let's take a simple example of a linked list with just two nodes, with values 1 and two. Then when reverseList is called, we can visualise the state like this:

 head
  ↓
┌────────────┐     ┌────────────┐
│ val: 1     │     │ val: 2     │
│ next: ──────────►│ next: NULL │
└────────────┘     └────────────┘ 

Then we have a recursive call where as argument a reference to the second node is passed. Inside that recursive call, this pointer is head. I'll call it head' (with apostrophe) here:

 head               head'
  ↓                  ↓
┌────────────┐     ┌────────────┐
│ val: 1     │     │ val: 2     │
│ next: ──────────►│ next: NULL │
└────────────┘     └────────────┘ 

Here we hit the base case and so the recursive call returns the reference to the second node, which in the calling context is assigned to p:

 head                p
  ↓                  ↓
┌────────────┐     ┌────────────┐
│ val: 1     │     │ val: 2     │
│ next: ──────────►│ next: NULL │
└────────────┘     └────────────┘ 

Then p->next=head is executed, and we get:

     head                p
      ↓                  ↓
    ┌────────────┐     ┌────────────┐
    │ val: 1     │     │ val: 2     │
 ┌─►│ next: ──────────►│ next: ─┐   │
 │  └────────────┘     └────────│───┘ 
 └──────────────────────────────┘

A cycle is created. And now, as return head is executed, we see the two problems occur: the wrong node reference is returned, and the cycle is not broken.

The following adapted code corrects both issues:

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL || head->next == NULL) return head;
    struct ListNode* newHead = reverseList(head->next);
    // The tail of the recursively reversed list is at head->next.
    //    Append the current node (head) at that tail
    head->next->next = head;
    // And terminate the list at the new tail:
    head->next = NULL;
    // Return the new head, not the old head
    return newHead;
}