x******0
发帖数: 1025 | 1 这个和我上学期考试题目一样啊
//recursively remove ALL nodes with value
PINTLISTNODE RemoveAll1(PINTLISTNODE pHead, int iRemoveValue)
{
if (pHead == NULL)
{
return NULL;
}
if (pHead->iValue == iRemoveValue)
{
PINTLISTNODE pToDelete = pHead;
pHead = pHead->pNext;
delete pToDelete;
return RemoveAll1(pHead, iRemoveValue);
}
else
{
pHead->pNext = RemoveAll1(pHead->pNext, iRemoveValue);
return pHead;
}
}
//use a dummyHead
PI... 阅读全帖 |
|
w****x
发帖数: 2483 | 2 //Merge two BST
//O(n) solution
//1. Change BST into linked list
//2. Merge 2 linked lists
//3. Change linked list into a balanced BST
struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};
////////////////////change BST to linked list///////////////////////////////
void _inner_chng_link(NODE* pNode, NODE*& ph, NODE*& pt)
{
if (NULL == pNode) return;
NODE* pLft1 = pNode;
NODE* pLft2 = pNode;
_inner_chng_link(pNode->pLft... 阅读全帖 |
|
w****x
发帖数: 2483 | 3
写一个
//Merge two BST
//O(n) solution
//1. Change BST into linked list
//2. Merge 2 linked lists
//3. Change linked list into a balanced BST
struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};
////////////////////change BST to linked list///////////////////////////////
void _inner_chng_link(NODE* pNode, NODE*& ph, NODE*& pt)
{
if (NULL == pNode) return;
NODE* pLft1 = pNode;
NODE* pLft2 = pNode;
_inner_chng_link(pNode-... 阅读全帖 |
|
w******g
发帖数: 189 | 4 贴一个以作参考：
DLNode * flatten_list(DLNode *head)
{
DLNode *p, *phead, *ptail;
p = head;
while(p->next){
p = p->next;
}
phead = head;
ptail = p;
while(phead->next != NULL){
if(phead->child != NULL){
ptail->next = phead->child;
phead->child->prev = ptail;
while(ptail->next != NULL){
ptail = ptail->next;
}
}
phead = phead->next;
}
return head;
} |
|
w****x
发帖数: 2483 | 5 NODE* SwapNodes(NODE* pHead)
{
assert(NULL != pHead);
if (pHead->pNext == NULL)
return pHead;
NODE* pRet = pHead->pNext;
NODE* pIter = pHead;
NODE* pPrev = NULL;
while (pIter != NULL && pIter->pNext != NULL)
{
if (NULL != pPrev)
pPrev->pNext = pIter->pNext;
NODE* pTmp = pIter->pNext->pNext;
pIter->pNext->pNext = pIter;
pIter->pNext = pTmp;
pPrev = pIter;
pIter = pIter->pNext;
}
return pRet;
} |
|
w****x
发帖数: 2483 | 6
以后面试因该严格静止用脚本语言面试,太坯了
NODE* Reverse(NODE* pHead, int nStart, int n)
{
if (NULL == pHead || nStart < 1 || n < 1)
return pHead;
NODE* pX = NULL;
NODE* pIter = pHead;
for (int i = 1; i < nStart && pIter != NULL; i++)
{
pX = pIter;
pIter = pIter->pNext;
}
if (pIter == NULL) return pHead;
NODE* pEnd = pIter;
NODE* pPrev = NULL;
for (int i = 0; i < n && pIter != NULL; i++)
{
NODE* pTmp = pIter->pNext;
pIter->pNext = p... 阅读全帖 |
|
w****x
发帖数: 2483 | 7
那是相当简洁啊~~~
全干掉：
/*
Given a sorted linked list, delete all duplicate numbers, leave only
distinct numbers from original list. e.g., given 1->2->3->3->4->4->5, return
1->2->5. Given 1->1->1->2->3, return 2->3.
*/
struct NODE
{
int nVal;
NODE* pNxt;
NODE(int n) : nVal(n), pNxt(NULL) {}
};
NODE* RemoveDupNodes(NODE* pHead)
{
assert(pHead);
NODE* pCur = pHead;
NODE* pPrev = NULL;
while (pCur != NULL)
{
NODE* pIter = pCur->pNxt;
bool bDel = false;
... 阅读全帖 |
|
w****x
发帖数: 2483 | 8
没意思
单链表的quick sort就可以了
struct NODE
{
int nVal;
NODE* pNext;
NODE(int n) : nVal(n), pNext(NULL) {}
};
void sort(NODE* pNode, int nLen)
{
if (NULL == pNode || nLen <= 0)
return;
int nCount = 0;
int nPivot = pNode->nVal;
NODE* pPrev = pNode;
NODE* pIterBeg = pPrev->pNext;
NODE* pIterEnd = pIterBeg;
while (NULL != pIterEnd)
{
if (pIterEnd->nVal < nPivot)
{
swap(pIterBeg->nVal, pIterEnd->nVal);
pPrev = pPrev-... 阅读全帖 |
|
x*********w
发帖数: 533 | 9 quick sort版本
struct NODE
{
int nVal;
NODE* pNext;
NODE(int n) : nVal(n), pNext(NULL) {}
};
void sort(NODE* pNode, int nLen)
{
if (NULL == pNode || nLen <= 0)
return;
int nCount = 0;
int nPivot = pNode->nVal;
NODE* pPrev = pNode;
NODE* pIterBeg = pPrev->pNext;
NODE* pIterEnd = pIterBeg;
while (NULL != pIterEnd)
{
if (pIterEnd->nVal < nPivot)
{
swap(pIterBeg->nVal, pIterEnd->nVal);
pPrev = pPrev->pNext;
... 阅读全帖 |
|
p*****3
发帖数: 488 | 10 给个我以前写的吧，快速排序版本的
struct NODE
{
int nVal;
NODE* pNext;
NODE(int n) : nVal(n), pNext(NULL) {}
};
void sort(NODE* pNode, int nLen)
{
if (NULL == pNode || nLen <= 0)
return;
int nCount = 0;
int nPivot = pNode->nVal;
NODE* pPrev = pNode;
NODE* ... 阅读全帖 |
|
w****x
发帖数: 2483 | 11 //How to find a value in a skip list
//about skip-list http://en.wikipedia.org/wiki/File:Skip_list.svg
struct SKIP_NODE
{
int nVal;
vector links;
};
//sort like binary search, scope down to decrease the searching range
SKIP_NODE* Find(SKIP_NODE* pHead, int x)
{
assert(pHead);
SKIP_NODE* pCur = pHead;
int nIndex = pHead->links.size() - 1;
while (nIndex >= 0)
{
if (pCur->nVal == x)
return pCur;
if (pCur->links[nIndex] == NULL ||
... 阅读全帖 |
|
w****x
发帖数: 2483 | 12 不用堆得版本：
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode *mergeKLists(vector &lists) {
ListNode* pHead = NULL;
ListNode* pIter = NULL;
while (true)
{
int p = -1;
for (int i = 0; i < lists.size(); i++)
{
if (lists[i] != NULL)
{
if (p < 0 || lists[i]->val < lists[p]->val)
p = i;
}
}
if (p < 0) break;
... 阅读全帖 |
|
w****x
发帖数: 2483 | 13
啊，不好意思，丢错版本了
struct NODE
{
int nVal;
NODE* pNext;
NODE(int n) : nVal(n), pNext(NULL) {}
};
NODE* mergeTwoList(NODE* p1, NODE* p2)
{
if (NULL == p1 && NULL == p2)
return NULL;
if (NULL == p1) return p2;
if (NULL == p2) return p1;
NODE* pIter1 = p1;
NODE* pIter2 = p2;
NODE* pIter = NULL;
NODE* pHead = NULL;
while (pIter1 != NULL && pIter2 != NULL)
{
NODE* pSmall = NULL;
if (pIter1->nVal < pIter2->nVal)
{
p... 阅读全帖 |
|
f********y
发帖数: 156 | 14 貌似 tail->up -> down。其实up / down 可以交换，你在flatten的时候先处理谁，那
么在unflatten也要先处理它。
Deflatten的唯一是因为 up / down 指针在flatten以后还保留着。flatten 只是把上
下层的表头连到了当前层的尾巴。
Deflatten的时候，觉得应该BFS。 貌似分层的问题，染色的问题，都是BFS。（ 楼主
原帖里的link 中有个递归做deflatten的函数，感觉不大对）
void deflatten(Node* pHead) {
if(! pHead ) {
return;
}
queue q;
q.push(pHead);
while(!q.empty()) {
Node* p = q.front();
q.pop();
while... 阅读全帖 |
|
l********n
发帖数: 1038 | 15 现有两种方法，一种递归，一种直接存指针反转。哪种好？
Java版
static List Reverse(List L)
{
//firstly check if L is empty or only has one element then return
if(L==null || L.next==null)
return L;
//otherwise, we can use our recursive method
List remainingReverse = Reverse(L.next);
//next we have two step steps, firstly we need update the tail of
remaining reverse as our head L
L.next.next = L;//this (L.next) is the key to get te tail in constant
time!
//Very important, we need set L.next ... 阅读全帖 |
|
S******A
发帖数: 1002 | 16 第一题应该是要求O(1)
pNext = remove->next;
remove->data=pNext->data;
remove->next = pNext->next;
delete pNext;
然后考虑remove == pHead
3 |
|
i*********h
发帖数: 49 | 17 【总结】Java 搞定链表-面试常考题目精选
面试大总结之链表：
一、OverView:
链表是面试中常考的，本文参考了其它一些文章，加上小编的自己总结，基本每个算法
都测试并优化过。
算法大全（1）单链表 中还有一些链表题目，将来也会整理进来。这些题目虽然简单，
但如果能毫无BUG地写出，定能让面试官司对您印象分大增。
小亮点是：主页君用Recursion 和 Iterator 各写了一次所有题目，这样就算遇到不熟
悉的写法，我们也都可以运用自如。
二、代码
以下是原文和代码：
http://weibo.com/3948019741/BseJ6ukI3
三、代码目录：
1. 求单链表中结点的个数:
getListLength
2. 将单链表反转:
reverseList（遍历），reverseListRec（递归）
3. 查找单链表中的倒数第K个节点（k > 0）:
reGetKthNode
4. 查找单链表的中间结点:
getMiddleNode
5. 从尾到头打印单链表:
reversePr... 阅读全帖 |
|
K**********i
发帖数: 22099 | 18 我的看法很复杂， 所以请你读完了再回复或者骂。
首先，我也不认为OCEF（或其领导阶层）是策动康妈募捐的始作俑者。是ACCEF，不是
OCEF。可以说，康妈案爆出后，ACCEF连敢出来洗地的都没有，某种程度上说明了他们
的心虚和胆怯；OCEF的义工发出不少声明，是支持康妈募捐的，有些人趁机做广告而已
（当然，这想法很奇特）。
我这种认知是建立在OCEF和ACCEF完全互相独立的基础上的。假设两个组织上面还有共
同的管理机构，那么我的认知就被推翻了。但这只是假设。
其次，我认为OCEF的义工，却的确在康妈案中扮演了不光彩的角色，使得我对OCEF的印
象大大下降。具体原因主要是顶着组织的名义，发表个人的宣言，很多帖都有讨论，不
展开了。
第三我认为是极少数重叠人员造成认知混乱，比如黑摸摸。我个人认为黑摸摸本人应该
又是OCEF的成员（亲口承认），又是ACCEF的成员或是至少是康妈募捐案的参与者（看
看她当时上蹿下跳以及对募捐的内行发言）。所以她具有双重身份。
比较耐人寻味的是黑摸摸发表的声明。大概意思我读出两条：（1）黑摸摸是OCEF义工
；（2）黑摸摸自己宣称没有参与康妈募捐（这条存疑，... 阅读全帖 |
|
G*O
发帖数: 706 | 19 【 以下文字转载自 Programming 讨论区 】
发信人: GTO (呵呵), 信区: Programming
标 题: 一道微软面试题
发信站: BBS 未名空间站 (Sun Aug 5 15:56:59 2007), 转信
Implement the following function for sorting a linked list of integers in
ascending order.
Your function should use only a constant amount of memory.
It's prohibited to change the value of ListNode, instead ListNodes must be
rearranged.
struct ListNode
{
int value() { return _value; }
ListNode *pNext;
private:
int _value;
};
ListNode* SortList(ListNode *pHead)
{
|
|
g*********h
发帖数: 21 | 20 我写的一个code，在debug的时候，运行到程序的最后，上面的code运行一切正常，但是
在退出main的时候，弹出一个窗口说Debug Assertion Failed!
Program:d:\test.exe
File:dbgdel.cpp
Line:52
Expression: _BLOCK_TYPE_IS_VALID(pHead->nBlockUse)
我不知道怎么回事，本人是新手，望指教！ |
|
c***d
发帖数: 996 | 21 ☆─────────────────────────────────────☆
GTO (呵呵) 于 (Sun Aug 5 15:56:59 2007) 提到:
Implement the following function for sorting a linked list of integers in
ascending order.
Your function should use only a constant amount of memory.
It's prohibited to change the value of ListNode, instead ListNodes must be
rearranged.
struct ListNode
{
int value() { return _value; }
ListNode *pNext;
private:
int _value;
};
ListNode* SortList(ListNode *pHead)
{
// Insert your implementation |
|
a***m
发帖数: 74 | 22 I used Visual C++ 2008 Express to build a simulation engine in win32 console
application.
My exe file was built successfully. It generated correct result. However,the
windows cmd window always pop up a message:
Debug Assertion Failed!
File: f:\dd\vctools\crt_bld\self_x86\crt\src\bdgbel.cpp
Line: 52
Expression: _BLOCK_TYPE_IS_VALID(pHead->nBlockUse)
I don't understand what caused the problem and how to solve the problem.
Any suggestions are welcome.
Thanks. |
|
x******a
发帖数: 6336 | 23 I defined a random number generator class norm, I would like to define a std
::vector of norm. However it did not work.
I got "Debug Assertation Failed" after the first of for loop.
Expression:_BLOCK_TYPE_IS_VALID(pHead->nBlockUse).
Any input are appreciated. Thanks!
code:
unsigned long seeds[]={123, 345, 356};
std::vector myseeds(std::begin(seeds), std::end(seeds));
std::vector mynorm;
for(auto it=myseeds.begin(); it!=myseeds.end(); ++it)
{
mynorm.push_back(norm(*it));
... 阅读全帖 |
|
a*********a
发帖数: 3656 | 24 you have got to take care of that GEN* gen. from stack overflow:
"The _BLOCK_TYPE_IS_VALID assertion gets fired, when you overwrite the
header of an block allocated by new. This happens when you slice objects,
use dead objects, etc."
"This type of error could be caused by Heap corruption."
my understanding is that you are overwriting the "gen" which is a pHead
pointing to a block on heap. that block is going to be lost. but I may be
wrong, since I have never seen such error messages before.
writ... 阅读全帖 |
|
