按相反顺序打印链表的后半部分

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