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的交換節點

回答

相關問題