c++ - 成对交换节点而不交换 LinkedList 中的数据

Question

我一直在尝试对链表元素进行成对交换。我不是通过数据交换元素，而是通过交换链接来交换它们:

输入 1:1->2->3->4->5 输出 1:2->1->4->3->5

输入 2:1->2->3->4->5->6 输出 2:2->1->4->3->6->5

#include <iostream>
using namespace std;

struct node{
  int data;
  struct node *next;
};

struct node* func(struct node *f, struct node *s){
    if(s==NULL){
        return f;
    }

    struct node *rest1;
    rest1 = s->next;

    s->next = f;
    if(rest1){
        f->next = func(rest1,rest1->next);
    }

    return s;
}

void show(struct node *head){
    while(head!=NULL){
        cout<<" "<<head->data;
        head = head->next;
    }
}

int main() {
    //code
    struct node *head  =(struct node*)malloc(sizeof(struct node));
    head->data=1;
    head->next = (struct node*)malloc(sizeof(struct node));

    head->next->data = 2;
    head->next->next = (struct node*)malloc(sizeof(struct node));

    head->next->next->data = 3;
    head->next->next->next = (struct node*)malloc(sizeof(struct node));

    head->next->next->next->data = 4;
    //head->next->next->next->next=(struct node*)malloc(sizeof(struct node));
    //head->next->next->next->next->data=5;

    head = func(head,head->next);
    show(head);
    return 0;
}

此代码适用于奇数长度列表，但不适用于偶数长度。 我认为问题出在:

if(s==NULL){
    return f;
}

我用来制作上一个 f->next=NULL 的语句(在偶数长度的情况下)。

Answer 1

既然你把它标记为 C++，我推荐 STL 的 <list> .你可以用它来完成你想要的 splice允许您操作列表的方法。一种可能的实现类似于:

void alternate(list<int>& l)
{
    if (l.empty())
        return;
    auto from_itr = cbegin(l);
    auto to_itr = from_itr;
    for (; ++to_itr != cend(l) && ++to_itr != cend(l);) {
        l.splice(to_itr, l, from_itr);
        ++from_itr;
    }
}

注意: from_itr在循环中只递增一次，因为它已在列表中移动到下一个感兴趣的节点之前。