C++ LinkedList的交换节点

-1

可能重复：
debug help - swap 2 nodes of double link list C++ LinkedList的交换节点

我试图写一个算法，可以在一个单链表在C++交换两个节点。这是我到目前为止有：

void swap(ListNode *node1, ListNode *node2) 
{ 
    ListNode *prev1 = head; 
    ListNode *prev2 = head; 

    //Search previous node for node1: 
    while(prev1->next!=node1 || prev1 != node1) 
     prev1 = prev1->getNext(); 

    //Search previous node for node2: 
    while(prev2->next!=node2 || prev2 != node2) 
     prev2 = prev2->getNext(); 


    if(node1->next==node2) 
    { //This means node1 == prev2? 
     tail = node1; 
     node1->next = NULL; 
     head = node2; 
     node2->next = node1; 
    } 
    else if(node2->next==node1) 
    { // node2 == prev1 
     tail = node2; 
     node2->next = NULL; 
     head = node1; 
     node1->next = node2; 
    } 
    if(node1->next == NULL) 
    { //node1 is last 
     node1->next = node2->next; 
     tail = node2; 
     node2->next = NULL; 
     prev1->next = node2; 
     prev2->next = node1; 
    } 
}

但我意识到，我可以得到的，就像如果有LL只有两个元素的不同案件的数量，或者如果他们给我们点2点1，等等等等，我之前意识到它不可能是复杂而丑陋的。那么如何编写一个交换两个节点的算法呢？

来源

2012-03-04 Richard

什么是* *的具体问题？ – 2012-03-04 16:13:27

我们不会在堆栈溢出（这不是网络论坛或留言板）上“提供一些提示”。我们回答有关编程语言的具体问题。 – 2012-03-04 16:13:51

“如何交换链接列表中的两个节点”听起来像是一个非常合法和具体的问题，虽然是重复的。 – tenfour 2012-03-04 16:19:37

在一个程序中完成整个任务是错误的。将其分解为两个更简单的问题：

1）从列表中删除节点，包括所有特殊情况。 2）在列表中插入节点，包括所有特殊情况。

从那里，总体问题很容易，但由于这显然是功课，你是自己的。

来源

2012-03-04 16:20:03 stark

-1

#include <stdio.h> 

struct llist { 
     struct llist *next; 
     char *payload; 
     } llists[]= 
{{ llists+1, "one"} 
,{ llists+2, "two"} 
,{ llists+3, "three"} 
,{ llists+4, "four"} 
,{ llists+5, "five"} 
,{ llists+6, "six"} 
,{ llists+7, "seven"} 
,{ llists+8, "eight"} 
,{ llists+9, "nine"} 
,{ NULL, "ten"} 
}; 

struct llist *head = llists; 

void llistswap(struct llist *one, struct llist * two) 
{ 
struct llist **hnd, **h1, **h2; 

h1 = h2 = NULL; 

for (hnd= &head; *hnd; hnd = &(*hnd)->next) { 
    struct llist *tmp; 
    if ((*hnd) == one) h1 = hnd; 
    else if ((*hnd) == two) h2 = hnd; 
    else continue; 
    if (!h1 || !h2) continue; 

    tmp = *h1; 
    *h1 = *h2; 
    *h2 = tmp; 

    tmp = (*h1)->next; 
    (*h1)->next = (*h2)->next; 
    (*h2)->next = tmp; 
    break; 
    } 
} 

void do_print(struct llist *lp) 
{ 
for (; lp; lp = lp->next) { 
    printf("%s%c", lp->payload, (lp->next) ?',' : '\n'); 
    } 
} 

int main(void) 
{ 
do_print (head); 
llistswap (llists+4, llists+7); 
do_print (head); 

return 0; 
}

来源

2012-03-04 16:21:05 wildplasser

OP询问一个双向链表，而不是单个链表。而且这个代码不足以说明任何内容。 – tenfour 2012-03-04 16:25:54

嗯，无论如何它都是作业，所以将更新添加到后台指示器（虽然我们处于此状态）看起来微不足道。 – wildplasser 2012-03-04 16:28:49

顺便说一句：标题和问题都没有提到双链表，也没有提到 - > prev指针。（有一些变量称为prev [12]，但这些似乎有其他目的） – wildplasser 2012-03-04 16:43:32

这似乎更清洁对我说：

//Maybe this function should go instide ListNode itself... 

ListNode *prev(ListNode *node) { 

    if (node == head) 
     return null; 

    ListNode *search = head; 

    while (search != node) 
     search = search->getNext(); 

    return search; 
} 

void swap(ListNode *node1, ListNode *node2) 
{ 
    ListNode *prev1 = prev(node1), 
      *prev2 = prev(node2), 
      *next1 = node1->getNext(), 
      *next2 = node2->getNext(); 

    if (prev1) 
     prev1->next = node2; 
    else 
     head = node2; 

    if (prev2) 
     prev2->next = node1; 
    else 
     head = node1; 

    if (!next1) 
     tail = node2; 
    else if (!next2) 
     tail = node1; 

    node1->next = next2; 
    node2->next = next1; 
}

没有测试OFC ...

来源

2012-03-04 16:32:54

C++ LinkedList的交换节点

回答

相关问题