草庐IT

c++ - 交换单个链表上的节点

coder 2024-01-30 原文

我正在尝试制作一个 swapNode 函数，它可以接受任意两个节点并交换它们。我已经制定了一种算法，如果它们至少相距 2 个节点，它就可以工作，但我似乎无法想出一种算法，如果它们彼此距离较近，它就可以工作。

到目前为止，这是我写的内容:

void swapNode(call * &head, call * &first, call * &second){
    call * firstPrev = NULL;
    call * secPrev = NULL;
    call * current = head;

    //set previous for first
    while((current->next != first) ){
        current = current->next;
    }

    firstPrev = current;
    current = head;

    //set previous for second
    while((current->next != second) ){
        current = current->next;
    }

    secPrev = current;
    current = second->next;

    //set firstPrev-> next to second
    firstPrev->next = second;
    //set secPrev->next to first
    secPrev->next = first;
    //set second->next = first->next
    second->next = first->next;
    //set first->next to current
    first->next = current;

    current = head;
    while(current->next != NULL){
        cout << current->number << endl;
        current = current->next;
    }

    cout << current->number << endl;
}

编辑: 我现在把它作为我的交换部分，但它似乎仍然无法正常工作

//swap firstPrev-> next with second->next
tmp = firstPrev->next;
second->next = firstPrev->next;
second->next = tmp;
//swap swap first->next with second->next
tmp = first->next;
second->next = first->next;
second->next = tmp;

编辑2: 这个似乎也不起作用，我遇到了段错误。

    //swap previous's->next
    tmp =firstPrev->next;
    secPrev->next = firstPrev->next;
    secPrev->next = tmp;
    //swap swap first->next with second->next
    tmp = first->next;
    second->next = first->next;
second->next = tmp;

最佳答案

假设我们有:

Node1 -> Node2 -> Node3 -> Node4 -> Node5

要交换两个节点，您需要交换每个节点之前的 next 值，以及要交换的节点的 next 值。

所以要交换，比方说，Node2 和 Node3，您实际上必须将 Node1->next 与 Node2->next 和 Node2->next 交换 和 Node3->next。这将起作用，即使它们彼此紧挨着(或者即使它是同一个节点)。例如:

交换 Node1->next 和 Node2->next

Node1->next = Node3
Node2->next = Node2

将 Node2->next 替换为 Node3->next

Node2->next = Node4
Node3->next = Node2

结果如下:

Node1 -> Node3 -> Node2 -> Node4 -> Node5

交换了!

正如 unwind 在评论部分指出的那样，如果将 Node1 与任何东西交换，您将必须为链表设置一个新的头。

回应问题的编辑:

你的交换代码几乎是正确的。但是，您需要将 firstPrev 与 secPrev 交换。在我的示例中，我们将节点的 next 值之一交换两次，因为它们彼此相邻。但从逻辑上讲，我们要交换前两个节点的 next，然后交换实际节点的 next。试试这个:

//swap firstPrev-> next with secPrev->next
tmp = firstPrev->next;
secPrev->next = firstPrev->next;
secPrev->next = tmp;
//swap swap first->next with second->next
tmp = first->next;
second->next = first->next;
second->next = tmp;

如果出现段错误，请检查 tmp 变量 - 它可能是某处的分配或删除错误。你从哪里得到段错误？

关于c++ - 交换单个链表上的节点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1535988/

amp43nextcodegtc++linked-listswap

有关c++ - 交换单个链表上的节点的更多相关文章

  1. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  2. ruby-on-rails - date_field_tag，如何设置默认日期？ [ rails 上的 ruby ] - 2

    我想设置一个默认日期，例如实际日期，我该如何设置？还有如何在组合框中设置默认值顺便问一下，date_field_tag和date_field之间有什么区别？ 最佳答案 试试这个:将默认日期作为第二个参数传递。youcorrectlysetthedefaultvalueofcomboboxasshowninyourquestion. 关于ruby-on-rails-date_field_tag，如何设置默认日期？[rails上的ruby]，我们在StackOverflow上找到一个类似的问

  3. ruby-on-rails - openshift 上的 rails 控制台 - 2

    我将我的Rails应用程序部署到OpenShift，它运行良好，但我无法在生产服务器上运行“Rails控制台”。它给了我这个错误。我该如何解决这个问题？我尝试更新ruby​​gems，但它也给出了权限被拒绝的错误，我也无法做到。railsc错误:Warning:You'reusingRubygems1.8.24withSpring.UpgradetoatleastRubygems2.1.0andrun`gempristine--all`forbetterstartupperformance./opt/rh/ruby193/root/usr/share/rubygems/rubygems

  4. ruby-on-rails - 相关表上的范围为 "WHERE ... LIKE" - 2

    我正在尝试从Postgresql表(table1)中获取数据，该表由另一个相关表(property)的字段(table2)过滤。在纯SQL中，我会这样编写查询:SELECT*FROMtable1JOINtable2USING(table2_id)WHEREtable2.propertyLIKE'query%'这工作正常:scope:my_scope,->(query){includes(:table2).where("table2.property":query)}但我真正需要的是使用LIKE运算符进行过滤，而不是严格相等。然而，这是行不通的:scope:my_scope,->(que

  5. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  6. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  7. ruby-on-rails - Ruby - 如何从 ruby​​ 上的 .pfx 文件中提取公钥、rsa 私钥和 CA key - 2

    我有一个.pfx格式的证书，我需要使用ruby​​提取公共(public)、私有(private)和CA证书。使用shell我可以这样做:#ExtractPublicKey(askforpassword)opensslpkcs12-infile.pfx-outfile_public.pem-clcerts-nokeys#ExtractCertificateAuthorityKey(askforpassword)opensslpkcs12-infile.pfx-outfile_ca.pem-cacerts-nokeys#ExtractPrivateKey(askforpassword)o

  8. 带有 attr_accessor 的类上的 Ruby instance_eval - 2

    我了解instance_eval和class_eval之间的基本区别。我在玩弄时发现的是一些涉及attr_accessor的奇怪东西。这是一个例子:A=Class.newA.class_eval{attr_accessor:x}a=A.newa.x="x"a.x=>"x"#...expectedA.instance_eval{attr_accessor:y}A.y="y"=>NoMethodError:undefinedmethod`y='forA:Classa.y="y"=>"y"#WHATTT?这是怎么回事:instance_eval没有访问我们的A类(对象)然后它实际上将它添加到

  9. ruby-on-rails - rails 上的 ruby : radio buttons for collection select - 2

    我有一个集合选择:此方法的单选按钮是什么？谢谢 最佳答案 Rails3中没有这样的助手。在Rails4中，它是collection_radio_buttons. 关于ruby-on-rails-rails上的ruby:radiobuttonsforcollectionselect，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/18525986/

  10. arrays - Ruby 数组 += vs 推送 - 2

    我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“

随机推荐