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 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 | 3
啊，不好意思，丢错版本了
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... 阅读全帖 |
|
w****x
发帖数: 2483 | 4
没意思
单链表的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 | 5 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 | 6 给个我以前写的吧，快速排序版本的
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* ... 阅读全帖 |
|
s*********e
发帖数: 17 | 7 I give you a singly linked Linked List. Write a function to swap every second
node. [ie - 1->2->3->4->5->| becomes 2->1->4->3->5->|]
大家有没有更好的办法？
BOOL SwapList(node** pphead)
{
if(*pphead == NULL)
return FALSE;
// two pointers
node* pNode1 = *pphead;
node* pNode2 = (*pphead)->pNext;
*pphead = pNode2;
while(pNode2->pNext != NULL)
{
// two temporay pointers
node* pTmp1 = pNode1->pNext->pNext;
node* pTmp2 = pNode2->pNext->pNext;
|
|
w****x
发帖数: 2483 | 8
以后面试因该严格静止用脚本语言面试,太坯了
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... 阅读全帖 |
|
S******A
发帖数: 1002 | 9 第一题应该是要求O(1)
pNext = remove->next;
remove->data=pNext->data;
remove->next = pNext->next;
delete pNext;
然后考虑remove == pHead
3 |
|
y****n
发帖数: 743 | 10 思路实现，没有编译运行：
Node* FindMergeNode(Node* pHeadA, Node* pHeadB)
{
Node* pTempA = pHeadA;
Node* pTempB = pHeadB;
int lenA = GetLength(pHeadA);
int lenB = GetLength(pHeadB);
for(int a=0; a < lenA-lenB; a++)
pTempA = pTempA -> pNext;
for(int b=0; b < lenB-lenA; b++)
pTempB = pTempB -> pNext;
while ((pTempB != null)&&(pTempA != pTempB))
{
if (pTempA == pTempB)
return pTempA;
pTempA = pTempA -> pNext;
pTempB = pTempB -> ... 阅读全帖 |
|
l********n
发帖数: 1038 | 11 现有两种方法，一种递归，一种直接存指针反转。哪种好？
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*********e
发帖数: 17 | 12 How can you print singly linked list in reverse order? (it's a huge list and
you cant use recursion) ?
大家有没有更好的方法 print “HUGE” list in reverse order? 谢谢！
BOOL ReverseList(node** pphead)
{
if(*pphead == NULL)
return FALSE;
node* pNode = NULL;
node* pTmp;
while(*pphead != NULL)
{
// tmp storage of header pointer
pTmp = (*pphead)->pNext;
// reverse
(*pphead)->pNext = pNode;
// pNode pointer moves one
|
|
G*O
发帖数: 706 | 13 【 以下文字转载自 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)
{
|
|
c***d
发帖数: 996 | 14 ☆─────────────────────────────────────☆
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 |
|
