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?
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
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...
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.
