3

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

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

这个结构就是链表的初始条件。我在想，当我们想要逆转时，会不会是这样；

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

因此，在一个需要O(n)运行时间的循环中，只需将节点 #1与节点 #5的数据反转，节点 #2与节点 #4就可以完成这项工作吗？

4

7 回答 7

4 
   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;
 }
于 2012-04-23T04:51:51.030 回答
3

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

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

于 2012-04-22T18:16:45.997 回答
3

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

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

您的算法失败了，因为您无法及时在单链表中倒退O(1)。按照你的建议做，它是O(n)每个节点（你每次从头一直走到你要获取前一个节点的地方），因此反转整个列表是O(n^2).

于 2012-04-22T18:16:56.710 回答
2

当被问到时，通常的限制是将列表反转到位，这样您就不会使用任何额外的空间，除了三个或更少的变量。这就是为什么这个问题不是微不足道的。因此，您既不能使用递归，也不能使用您自己的显式堆栈，也不能使用另一个 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)

于 2012-04-23T00:31:48.250 回答
1

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

  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  
  }
}
于 2012-04-22T19:35:05.617 回答
1

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

于 2012-04-22T18:20:25.523 回答
1

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

struct base {
   int type;
   struct base *next;
   };

struct small {
   struct base common;
   int value;
   };

struct big {
    struct base common;
    char payload[12345];
    };
于 2012-04-22T18:28:53.290 回答