algorithm - 如何在不修改指针的情况下递归地反转单链表？

Question

最近面试，面试官让我在不修改指针(只改变值)的情况下反转一个单向链表。一开始我想出了一个使用堆栈的解决方案。他说没关系，并希望我递归地做。然后我给了他一个O(n^2)的解。但是他说他需要一个 O(n) 的解决方案。

谁能帮帮我？

Answer 1

伪代码

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