CODEWITHSUNDEEP
algorithmrecursionlinked-list
lyc0530
lyc0530

Reputation: 13

How to reverse a singly linked list recursively without modifying the pointers?

Recently I had an interview and the interviewer asked me to reverse a singly linked list without modifying the pointers(change the values only). At the beginning I came up with a solution using a stack. He said that was OK and wanted me to do it recursively. Then I gave him a O(n^2) solution. But he said he needs a O(n) solution.

Anyone can help me?

Upvotes: 0

Views: 110

Answers (3)

n. m. could be an AI
n. m. could be an AI

Reputation: 119877

Pseudocode

reverse (list):
 reverse2 (list, list)

reverse2 (a, b):
 if b != nil:
  a = reverse2 (a, b.next)
  if a != nil:
   swap (a.data, b.data)
   if a == b || a.next == b:
    # we've reached the middle of the list, tell the caller to stop
    return nil
   else:
    return a.next
  else:
   # the recursive step has returned nil, they don't want us to do anything
   return nil
 else:
  # we've reached the end of the list, start working!
  return a

Upvotes: 1

Carlos Romero
Carlos Romero

Reputation: 720

list = { a => b => c => d }

def recursive(acc, x)
  if !x
    return acc
  end
  acc.preprend(x)

  return recursive(acc, x.next)
end

result = recursive([], list.first)

So first call is recursive([], a). result is now [a].

Second call is recursive([a], b). result turns into [b, a].

Third call is recursive([b, a], c). result is [c, b, a].

Fourth call is recursive([c, b, a], d), and result [d, c, b, a].

Fifth call gets caught by the if !x.

Tell your interviewer you need an additional structure, like someone else said above.

Upvotes: 0

sashang
sashang

Reputation: 12194

One way I can think of doing it is recursing to the end accumulating the values in another list as you resurse to the end, then on the way out of the recursion writing the values back starting with the 1st value in the list. It would be O(2n). It's not much different from using a stack...

Upvotes: 1

Related Questions