请教两个算法问题.

okdavinci

1: 怎么在Ｏ（ｎ）复杂度下,实现对单连表数据元素的旋转?
2:怎么用一个指针实现双向连表?
以上问题来自<<算法导论>>谢谢.

converse

1.“旋转”应该是“逆转”吧？
2.多加一个指针我不知道是不是指在每个链表的节点里面加一个指向前一个元素的指针呢？这样子显然是可以变成双向链表的了

linyue

原帖由 okdavinci 于 2007-1-14 15:34 发表
1: 怎么在Ｏ（ｎ）复杂度下,实现对单连表数据元素的旋转?
2:怎么用一个指针实现双向连表?
以上问题来自<<算法导论>>谢谢.

第一个用一个栈就行了
第二个没看懂

DraculaW

1: 怎么在Ｏ（ｎ）复杂度下,实现对单连表数据元素的旋转?

非常简单 基本上

2:怎么用一个指针实现双向连表?

-_-！  难道是环琏然后要移到前m个就向后移动n-m次

tyc611

原帖由 okdavinci 于 2007-1-14 15:34 发表
1: 怎么在Ｏ（ｎ）复杂度下,实现对单连表数据元素的旋转?
2:怎么用一个指针实现双向连表?
以上问题来自<<算法导论>>谢谢.

估计你没看懂原文
1. 要实现链表逆转，可以设置几个辅助变量就行，比如：
struct Node {
   Data data;
   struct Node* next;
};
struct Node* pHead; //initialize it
struct Node* pHead2 = NULL, pTmp;

while (pHead != NULL) {
   pTmp = pHead;
   pHead = pHead->next;
   pTmp->next = pHead2;
   pHead2 = pTmp;
}
pHead = pHead2;

2. 如果只是一个指针，实现的只能是循环链表，没法双向

ArXoR

第二个问题:

1. 
   
2. 每个节点保存一个值为 val = pre ^ next
   
3. 操作过程中我们总是保存着当前节点的next值
   
4. 
   
5. 当前节点地址为addr
   
6. 
   
7. 移向后继:
   
8. temp <- next
   
9. next <- next.val ^ addr
   
10. addr <- temp
    
11. 
    
12. 移向前驱:
    
13. temp <- addr
    
14. addr <- addr.val ^ next
    
15. next <- temp
    

复制代码

当然这样做的代价是不能随机根据节点地址取得前驱.
题目的本意应该是减少每个节点链表指针的情况下能支持大部分双向链表的操作

Please correct me if I'm wrong.