单向链表的逆序解决办法

2012-05-14

单向链表的逆序struct node{void* nextint data}struct list{node* headlist(){ headnew node()}~li

单向链表的逆序
struct node
{

void* next;
int data;

};

struct list
{

node* head;

list(){ head=new node();}

~list() { clear(); };

其他函数.................

};

void Reverse(list& another)
{
........
};

完善函数Rerverse，实现将 list逆序，注意：list是单向的，不是“逆序输出”，是将整个链表翻转。

我的思路：

对比数组逆序，采用指针进行首尾扫描，一个向前，一个向后，进行交换数据。后来我发现是不行的，因为是单向，链表无法做到向后扫描！！！！

不知道谁有思路解决这个问题。。。。

提供代码，谢谢了啊。

[解决办法]
最简单的方法是后一个节点不停的往前（指表头）插入
比如：1 2 3 4
2往前插后形成：2 1 3 4
3再往前插后形成： 3 2 1 4
4再往前插后就是 4 3 2 1 了这个实现代码很容易的
[解决办法]
if (another.head = 0) //空表检查
第一句写错
if (!another.head)
或者
if (another.head == 0)

[解决办法]

探讨

我提供一个思路吧，楼主，采用头插法建立链表的方式进行。首先从已有链表的头结点开始。然后顺序遍历，每次遍历一个节点，把这个节点放置在新链表的头结点后面。这样就完成了倒置了。

[解决办法]
我直接抄自《算法：C语言实现》中文版第55页。此书网上有电子版。

C/C++ code

void Reverse(list& another) {    node* p, *q=NULL,*head;    head=another.head->next;     while(head!=NULL) {       p=head->next; head->next=q; q=head; head=p;    }    another.head->next=q;}
[解决办法]
node* Reverse(list* L)
  {
   node* LP,*LN,*Head;
  
   LP=L;
   LN=L->next;
   L->next=null;//将第一个节点的next清空

   while (LN !=null)
   {
      Head=LN;
      LN=Head->next;
      Head->next=LP;   
      LP=Head;
   }
   return Head;
}

热点排行