反转链表的程序__解释一下，详细点吧，我不聪明
这几天我都在弄这个，我真的很笨，详细一点解释吧，指针转向的问题
class DLList{
public:
DLList(){ head = tail = 0; }
void R(){
reverse( head );
DLLNode * tmp;
tmp = head;
head = tail;
tail = tmp;
tail -> next = 0;
}
void addtotail( int & n);
void print();
protected:
void reverse( DLLNode * n );
DLLNode * head, * tail;
};
[解决办法]
这个问题还在啊?!
我给个详细点的解释吧:
假设链表的结构为:
struct Node { int item; Node* next; };
单向链表是一个有序的序列.假设有一个单向链表A:
1, 2, 3, 4, 5, ...
现在将A表逆序后得到链表B:
..., 5, 4, 3, 2, 1
// 常规的反转链表方法
Node *reverse(Node *list)
{
link t, y = list, r = 0;
while (y != 0) { t = y-> next; y-> next = r; r = y; y = t; }
return r;
}
其实上面的这个操作自然地对应于栈的出栈/压栈操作.
因此, 单向链表的逆序问题我们也可以抽象为A和B两个
栈的转换问题.
现在给Node实现用于栈的操作函数:
// 1. 判断栈是否为空
bool isEmpty(Node* stack)
{
return (stack == NULL);
}
// 2. 向栈stack中压入一个node元素
void push(Node* &stack, Node* node)
{
node-> next = stack;
stack = node;
}
// 3. 从栈stack中弹出一个元素
Node* pop(Node* &stack)
{
assert(!isEmpty(stack));
Node *t = stack;
stack = stack-> next;
return t;
}
下面可以基于栈实现单向链表的逆序操作了.
Node *reverse(Node *oldList)
{
Node *newList = NULL;
while(!isEmpty(oldList))
{
push(newList, pop(oldList));
}
return newList;
}
采用栈的思维来思考单向链表的逆序问题之后,许多本来
相对复杂的问题都会变得异常简单. 例如, 我们现在再
考虑用递归的方法来逆序链表.
// 递归实现反转链表
Node *reverse(Node *oldList, Node *newList=NULL)
{
// 判断oldList是否为空
if(isEmpty(oldList)) return newList;
// 从oldList栈弹出一个元素
// 然后将弹出的元素压到newList栈中
push(newList, pop(oldList));
// 递归处理剩下的oldList链表
return reverse(oldList, newList);
}
// 递归版本的调用方式
int main()
{
Node *list = NULL;
// newList采用默认的NULL
Node *t = reverse(list);
// ...
}
http://www.google.com/notebook/public/07623680211395710736/BDSHRIgoQqe_l_Jsi?hl=zh-CN
http://blog.csdn.net/chai2010/
