15道简单算法题(附源代码第二部分)
4:给定一个单链表的头指针和一个指定节点的指针，在O(1)时间删除该节点; 删除节点的核心还是将这个节点的下一个节点，代替当前节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
//给定一个单链表的头指针和一个指定节点的指针，在O(1)时间删除该节点
void DeleteNode(NodeL* head,NodeL* delNode)
{
if (!head || !delNode)
{
return;
}
if (delNode->next!=NULL)//删除中间节点
{
NodeL* next=delNode->next;
delNode->next=next->next;
delNode->value=next->value;
delete next;
next=NULL;
}else if (head==delNode)//删除头结点
{
delete delNode;
delNode=NULL;
*head=NULL;
}else//删除尾节点，考虑到delNode不在head所在的链表上的情况
{
NodeL* tmpNode=head;
while (tmpNode && tmpNode->next!=delNode)
{
tmpNode=tmpNode->next;
}
if (tmpNode!=NULL)
{
delete delNode;
delNode=NULL;
tmpNode->next=NULL;
}
}
}
void DeleteNodeTest()
{
int nodeCount=10;
for (int K=0;K<nodeCount;K++)
{
NodeL* head=NULL;
NodeL* cur=NULL;
NodeL* delNode=NULL;
for (int i=0;i<nodeCount;i++)
{
NodeL* tmpNode=new NodeL(i);
if (i==0)
{
cur=head=tmpNode;
}else{
cur->next=tmpNode;
cur=tmpNode;
}
if (i==K)
{
delNode=tmpNode;
}
}
DeleteNode(head,delNode) ;
}
}
5:找到链表倒数第K个节点; 通过两个指针，两个指针都指向链表的开始，一个指针先向前走K个节点，然后再以前向前走，当先走的那个节点到达末尾时，另一个节点就刚好与末尾节点相差K个节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//找到链表倒数第K个节点
NodeL* FindKthToTail(NodeL* head,unsigned int k)
{
if(head==NULL || k==0)
return NULL;
NodeL* tmpNode=head;
for (int i=0;i<k;i++)
{
if (tmpNode!=NULL)
{
tmpNode=tmpNode->next;
}else{
return NULL;
}
}
NodeL* kNode=head;
while (tmpNode!=NULL)
{
kNode=kNode->next;
tmpNode=tmpNode->next;
}
return kNode;
}
void FindKthToTailTest()
{
int nodeCount=10;
for (int K=0;K<nodeCount;K++)
{
NodeL* head=NULL;
NodeL* cur=NULL;
for (int i=0;i<nodeCount;i++)
{
NodeL* tmpNode=new NodeL(i);
if (i==0)
{
cur=head=tmpNode;
}else{
cur->next=tmpNode;
cur=tmpNode;
}
}
NodeL* kNode=FindKthToTail(head,K+3) ;
if (kNode)
{
cout<<"倒数第 "<<K+3<<" 个节点是："<<kNode->value<<endl;
}else{
cout<<"倒数第 "<<K+3<<" 个节点不在链表中"<<endl;
}
}
}
6:反转单链表; 按顺序一个个的翻转就是了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//反转单链表
NodeL* ReverseList(NodeL* head)
{
if (head==NULL)
{
return NULL;
}
NodeL* reverseHead=NULL;
NodeL* curNode=head;
NodeL* preNode=NULL;
while (curNode!=NULL)
{
NodeL* nextNode=curNode->next;
if (nextNode==NULL)
reverseHead=curNode;
curNode->next=preNode;
preNode=curNode;
curNode=nextNode;
}
return reverseHead;
}
void ReverseListTest()
{
for (int K=0;K<=10;K++)
{
NodeL* head=NULL;
NodeL* cur=NULL;
for (int i=0;i<K;i++)
{
NodeL* tmpNode=new NodeL(i);
if (i==0)
{
cur=head=tmpNode;
}else{
cur->next=tmpNode;
cur=tmpNode;
}
}
cur=ReverseList( head);
while (cur)
{
cout<<cur->value<<" ";
cur=cur->next;
}
cout<<endl;
}
cout<<endl;
}
7:通过两个栈实现一个队列; 直接上代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
//通过两个栈实现一个队列
template<typename T>
class CQueue
{
public:
void push(const T& val)
{
while (s2.size()>0)
{
s1.push(s2.top());
s2.pop();
}
s1.push(val);
}
void pop()
{
while (s1.size()>0)
{
s2.push(s1.top());
s1.pop();
}
s2.pop();
}
T& front()
{
while (s1.size()>0)
{
s2.push(s1.top());
s1.pop();
}
return s2.top();
}
int size()
{
return s1.size()+s2.size();
}
private:
stack<T> s1;
stack<T> s2;
};
void CQueueTest()
{
CQueue<int> q;
for (int i=0;i<10;i++)
{
q.push(i);
}
while (q.size()>0)
{
cout<<q.front()<<" ";
q.pop();
}
}
谢谢楼主分享！！！！！！！！！！ 我只是路过打酱油的。
页:
[1]