如何确定这两种双链表算法的space和时间复杂度？

Question

我用两个解决方案解决了下一个练习：https://www.hackerrank.com/challenges/reverse-a-doubly-linked-list

首先（非递归）：

/*
  Insert Node at the end of a linked list 
  head pointer input could be NULL as well for empty list
  Node is defined as 
  class Node {
     int data;
     Node next;
     Node prev;
  }
*/

Node Reverse(Node head) {
    if (head == null) return null;

    Node current = head;

    while (current.next != null) {
        Node temp = current.next;
        current.next = current.prev;
        current.prev = temp;

        current = temp;
    }

    current.next = current.prev;
    current.prev = null;

    return current;
}

第二种算法（递归）：

/*
  Insert Node at the end of a linked list 
  head pointer input could be NULL as well for empty list
  Node is defined as 
  class Node {
     int data;
     Node next;
     Node prev;
  }
*/

Node Reverse(Node head) {
    if (head.next == null) {
        head.next = head.prev;
        head.prev = null;
        return head;
    }

    Node newHead = Reverse(head.next);

    Node temp = head.next;
    head.next = head.prev;
    head.prev = temp;

    return newHead;
}

按照书上的说法，解一定是O(n)。我想使用递归解决方案更优雅，但也许我错了。您能否帮助确定这两个算法的 space 和时间复杂度，或者在您的算法中，哪个性能更好？

Answer 1

这个问题有点不清楚，两个解决方案在时间和space上似乎都是O(n)。尽管您可能会删除特殊情况并让 Torvalds 高兴。类似于：

Node Reverse(Node head) {
  if (head == null) return null;

  Node current = head;

  while (current != null) {
    Node temp = current.next;
    current.next = current.prev;
    current.prev = temp;

    current = temp;
}
return current;

}

Node Reverse(Node head) {
   Node temp = head.next;
   head.next = head.prev;
   head.prev = temp;

   return temp==null?head:Reverse(temp);

}

我没有测试过这些，仅供参考。（如果 head 在开始时为 null，则递归将为 nullpointer）。

如何确定这两种双链表算法的space和时间复杂度？

How to determine the space and time complexity of these two double linked list algorithms?

java

algorithm

time-complexity

big-o

space-complexity