按相反順序打印鏈表的後半部分

Question

我想打印一個鏈表的元素，首先按順序打印，然後一旦到達中間，按照相反的順序（從最後一個向後）打印。例如：

如果內容是：1 2 3 4 5 6
它應該打印：1 2 3 6 5 4
但它的打印：1 2 3 5 4

爲什麼不將它打印的最後一個元素？這怎麼解決？

void reverse() 
{ 
    int c=1; 
    node *current,*prev,*temp; 
    current=head; 
    prev=NULL; 
    std::stack<int>s; 
    while(current->next!=NULL) 
    { 
     c++; 
     s.push(current->data); 
     current=current->next; 
    } 

    int mid=0; 
    if((c%2)==0) 
    { 
     mid=c/2; 
    } 
    else 
    { 
     mid=(c+1)/2; 
    } 
    current=head; 
    for(int i=0;i<mid;i++) 
    { 
     cout<<current->data<<"\t"; 
     current=current->next; 
    } 

    for(int i=mid;i>1;i--) 
    { 
     std::cout<<s.top()<<"\t"; 
     s.pop(); 
    } 
    std::cout << '\n'; 
} 

Answer 1

工作代碼： http://ideone.com/bbzsSy

2個問題：

• while(current->next!=NULL)應該是：while(current!=NULL)
  氏通過這種方式，你可以確定你可以解引用指針，並且還可以推送最後一個節點。

• for(int i=0;i<mid;i++)應該是：for(int i=0;i<lastFordward;i++)
  凡lastFordward=(c%2)?mid-1:mid;
  這樣避免打印中間位置時，兩次是c連。

Answer 2

在你while循環要檢查是否current->next是null你需要檢查，如果current是null。

while(current) 
{ 
    c++; 
    s.push(current->data); 
    current=current->next; 
} 

你沒有添加的最後一個數字爲stack

Answer 3

這種方法可以工作...聲明一個函數來獲取的鏈表

public int size() 
{ 
    int counter = 0; 
    node *nodePtr = head; 

    while (nodePtr) 
    { 
     if (nodePtr->next != null) 
     { 
      counter++; 
     } 
    } 

    return counter; 
} 

那麼大小，如果大小返回是偶數...

int c = size()/2; 

其他...

int c = (size()+1)/2; 

然後初始化和數組，並反向打印出來....嘗試一下可能的工作:)

Answer 4

在一個典型的鏈表實現的最後一個節點指向任何操作（通常nullptr）。因此，將現有元素（current-> next！= nullptr）添加到堆棧的停止條件不包含最後一個元素。

迭代過電流將是一種更好的方法，因爲它會在最後一個節點之後停止。

另請注意，這將對您的中點計算產生影響，因爲它從一開始就偏離了一點。

Answer 5

這不是很會編，但這是有點少行：

// assert myList is sorted before called 
// if it's not, add  
// std::sort(myList.begin(), myList.end()); 
// as the first line of the function 
void reverseLatterHalf(std::vector& myList) { 
    auto it = myList.begin() + myList.size()/2; 
    std::reverse(it, myList.end()); 
} 

Answer 6

假設該列表僅包含一個元素。在這種情況下，這個循環

while(current->next!=NULL) 
{ 
    c++; 
    s.push(current->data); 
    current=current->next; 
} 

將永遠不會執行，因此堆棧將爲空。此外，當列表依次爲空且因此head等於NULL並且您可能無法訪問current->next數據成員時，該函數最初具有未定義的行爲。

現在我們假設該列表恰好包含兩個元素。循環將只執行一次，變量c的值爲2.變量mid的計算值將等於1。

所以該環路

for(int i=0;i<mid;i++) 
{ 
    cout<<current->data<<"\t"; 
    current=current->next; 
} 

只執行一次迭代和第一元件被輸出。

然而下一循環

for(int i=mid;i>1;i--) 
    { 
    std::cout<<s.top()<<"\t"; 
    s.pop(); 


    } 

意願;因爲它的條件i > 1得到false，因爲mid等於1.

所以程序有兩個錯誤循環，應該被重寫。

下面是一個演示程序，顯示如何實現該功能。

#include <iostream> 
#include <stack> 

struct node 
{ 
    int data; 
    node *next; 
} *head = nullptr; 

void append(int data) 
{ 
    node **current = &head; 

    while (*current) current = &(*current)->next; 

    *current = new node { data, nullptr }; 
} 

void clear() 
{ 
    while (head) 
    { 
     node *tmp = head; 
     head = head->next; 
     delete tmp; 
    } 
} 

void reverse() 
{ 
    std::stack<int> s; 

    for (node *current = head; current; current = current->next) 
    { 
     s.push(current->data); 
    } 

    std::stack<int>::size_type middle = (s.size() + 1)/2; 
    std::stack<int>::size_type i = 0; 

    for (node *current = head; i < middle; i++) 
    { 
     std::cout << current->data << '\t'; 
     current = current->next; 
    } 

    for (i = s.size() - i; i != 0; i--) 
    { 
     std::cout << s.top() << '\t'; 
     s.pop(); 
    } 

    std::cout << std::endl; 
} 

int main() 
{ 
    const int N = 10; 

    for (int i = 0; i < N; i++) 
    { 
     for (int j = 0; j <= i; j++) append(j); 
     reverse(); 
     clear(); 
     std::cout << std::endl; 
    } 

    return 0; 
} 

程序輸出是這裏

0 

0 1 

0 1 2 

0 1 3 2 

0 1 2 4 3 

0 1 2 5 4 3 

0 1 2 3 6 5 4 

0 1 2 3 7 6 5 4 

0 1 2 3 4 8 7 6 5 

0 1 2 3 4 9 8 7 6 5