与链表反转有关的想法

Question

自从我听说在采访中被问到很多问题以来，有些事情一直困扰着我。反转单向链表。问题是我已经检查了实现，我想知道我的想法是否可以应用。

|data1|->|data2|->|data3|->|data4|->|data5|

此结构是链表的初始条件。我在想，当我们想要逆转时，会不会像;

|data5|->|data4|->|data3|->|data2|->|data1|

因此，在需要 O（n） 运行时间的循环中，只需将节点 #1 的数据与节点 #5、节点 #2 与节点 #4 反转

Answer 1

   typedef struct Node
   {
     char data;
     struct Node* next;
   } Node; 

    Node* reverse(Node* root)
    {
       Node* new_root = 0;
       while (root)
       {
           Node* next = root->next;
           root->next = new_root;
           new_root = root;
           root = next;
       }
       return new_root; 
    } 

int main()
{
   Node d = { 'd', 0 };
   Node c = { 'c', &d };
   Node b = { 'b', &c };
   Node a = { 'a', &b };
   Node* root = &a; 
   root = reverse(root);
   return 0;
 }

Answer 2

你想insert_head编写一个方法并重复使用它。因此，您从原始列表的头部开始，并附加到新链表的头部。因此，原始列表的尾部将成为新列表的头部。

这是另一种方法：遍历原始列表，将节点推送到堆栈上。然后，当您进入新列表时弹出并insert_at_tail。

你的算法失败了，因为你不能在O(1)时间内在单向链表中向后走。要按照您的建议进行操作，每个节点都是O(n)（您每次都从头部一直走到您所在的位置以获取前一个节点），因此反转整个列表是O(n^2)。

Answer 3

您的算法要求我们从节点 5 开始，然后从那里向后工作。 但它是一个单链列表 - 这意味着我们没有"后退"指针。 即使我们对tail节点有 O（1） 访问权限，从节点 5 到节点 4 本身就是一个 O（N） 操作，因为我们需要从节点 1 重新开始才能到达节点 4。

因此，对于单向链表来说，这不是一个好的算法。 对于一个双向链表，我们可以访问反向指针，它会给我们带来 O（N） 的复杂性。 （您的算法也不是完全与类型无关的，因为它要求存储在每个节点中的数据是可复制或可移动的，以便我们可以交换它。

Answer 4

当被问到时，通常的限制是就地反转列表，这样除了三个或更少的变量之外，您不会使用任何额外的空间。这就是为什么这个问题不是微不足道的。因此，您既不能使用递归，也不能使用自己的显式堆栈或另一个LL（在浏览原始堆栈时LL.addToHead(el)

）。

所以这里有一个很好的答案 O（n） 时间和 O（1） 空间：

Node reverse(Node n){//n is head; you may also get the LL
    if(null == n || null == n.next)
       return n;
    Node a=n, b=a.next, c=b.next;
    a.next=null; b.next=a;
    while(null != c){
       a=c;
       c=c.next;
       a.next=b;
       b=a;
    }
    return b;
}

顺便说一下，你提出的解决方案是 O（n^2）

Answer 5

有一个使用O(n)空间的O(n)解决方案。考虑避免线性时间访问元素的问题。

Answer 6

如果列表是异构的，或者节点大小不相等，这个想法就会惨败。举个例子：

struct base {
   int type;
   struct base *next;
   };
struct small {
   struct base common;
   int value;
   };
struct big {
    struct base common;
    char payload[12345];
    };

Answer 7

仅

根据节点在最终输出中的位置从节点反转数据不是一个好主意，原因有两个：

1. 如果列表很大，这将不是一个可行的解决方案
2. 以任意方式访问节点的时间更多。该方法将比 O（n） 花费更多时间。

请考虑以下伪代码：

reverse_list(node *head) 
{
  node *temp;
  *temp = head -> next;
  head-> next = NULL;
  while (temp != NULL) {
     swap_nodes(head, temp->next);  // this aint copying data from nodes, actual nodes are 
     swap_nodes(head, temp);        // swapped based on its and parents' next pointers  
  }
}