最近面试,面试官让我在不修改指针(只改变值)的情况下反转一个单向链表。 一开始我想出了一个使用堆栈的解决方案。他说没关系,并希望我递归地做。然后我给了他一个O(n^2)的解。但是他说他需要一个 O(n) 的解决方案。
谁能帮帮我?
最佳答案
伪代码
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
关于algorithm - 如何在不修改指针的情况下递归地反转单链表?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35307526/