使用指針

-1

反向列表的元素

可能重複：
How to read a singly linked list backwards?
Reverse a LinkedList c++使用指針

我怎樣才能reverse一個連接list的元素，而無需使用arrays

（我不得不使用指針這是我的問題）。

來源

2012-11-02 MKB

「我只使用指針這就是我的問題「 - 原始指針？然後你寫C，關於你的問題，如果它是一個單獨鏈表，那麼通過遍歷一次就無法避免O（n）的複雜性。如果它是一個雙向鏈表，那麼你可以在相反的方向上遍歷它。 –

也許[這個答案]（http://stackoverflow.com/a/13033927/596781）可以幫助... –

@MihaiTodor所以STL/Boost不是C++？離開它。 – James

將列表視爲堆棧，將元素彈出並將其推入新列表。

來源

2012-11-02 17:46:08 SpacedMonkey

我認爲他寧願做更多「就地」的手術，以保存記憶。爲此，他將需要兩個輔助指針指向當前節點和前一個節點，並在遍歷列表一次時更新節點之間的鏈接。 –

求索列表稱爲lst這使我們能夠向前向後，即它是doubly linked list

您可以通過簡單地交換開始的內容和終端節點反向列表lst

void reverse(lst *beg,lst *end) 
{ 
    lst temp; 
    while(beg!=end) 
    { 
     //swap the content of the nodes 
     *temp=*beg; 
     *beg=*end; 
     *end=*temp; 

     beg=beg->Next();//move to next node 
     end=end->prev();//move to previous node 
    } 
}

或

如果它是一個singly linked list，你可以使用stack

void reverse(lst* beg) 
{ 
    stack<lst*> stc; 
    lst* temp=beg; 
    lst* temp1=beg; 
    while(temp)//store pointers to lst nodes in stack 
    { 
     stc.push(temp); 
     temp=temp.Next(); 
    } 
    while(temp1)//pop the stack by inserting it into list from beginning 
    { 
     *temp1=*stc.top(); 
     temp1=temp1.Next(); 
     stc.pop(); 
    } 
}

來源

2012-11-02 17:49:30 Anirudha

「只需使用列表容器類的C++」 - 他可能不希望這樣，因爲它是一個雙向鏈表，這並不總是表現密碼的最佳選擇來實現。 –

你既不需要交換節點內容或堆棧。如果你想反轉一個單鏈表，只需在迭代循環中用一對指針加上中間指針就行。當你完成時不要忘記更新頭指針;

void reverse_list(node **head) 
{ 
    node *cur=NULL, *nxt=NULL; 

    if (!(head || *head || (*head)->next)) 
     return; 

    nxt = *head; 
    while (nxt != NULL) 
    { 
     node *prv = cur; 
     cur = nxt; 
     nxt = nxt->next; 
     cur->next = prv; 
    } 

    *head = cur; 
}

假設列表節點是這樣的：

typedef struct node 
{ 
    ..data.. 
    struct node *next; 
} node;

和管理得當，那麼你調用這樣：

node *head = NULL; 

...fill the list... 

reverse_list(&head);

來源

2012-11-02 19:41:30 WhozCraig

回答

相關問題