15道简单算法题(附源代码第二部分)

H9enRy · 发表于 2014-8-1 00:27:02

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

　　4:给定一个单链表的头指针和一个指定节点的指针，在O(1)时间删除该节点;

　　删除节点的核心还是将这个节点的下一个节点，代替当前节点。

[backcolor=white !important][size=1em]

[size=1em]1

[size=1em]2

[size=1em]3

[size=1em]4

[size=1em]5

[size=1em]6

[size=1em]7

[size=1em]8

[size=1em]9

[size=1em]10

[size=1em]11

[size=1em]12

[size=1em]13

[size=1em]14

[size=1em]15

[size=1em]16

[size=1em]17

[size=1em]18

[size=1em]19

[size=1em]20

[size=1em]21

[size=1em]22

[size=1em]23

[size=1em]24

[size=1em]25

[size=1em]26

[size=1em]27

[size=1em]28

[size=1em]29

[size=1em]30

[size=1em]31

[size=1em]32

[size=1em]33

[size=1em]34

[size=1em]35

[size=1em]36

[size=1em]37

[size=1em]38

[size=1em]39

[size=1em]40

[size=1em]41

[size=1em]42

[size=1em]43

[size=1em]44

[size=1em]45

[size=1em]46

[size=1em]47

[size=1em]48

[size=1em]49

[size=1em]50

[size=1em]51

[size=1em]52

[size=1em]53

[size=1em]54

[size=1em]55

[size=1em]56

[size=1em]57

[size=1em]58

[size=1em]59

[size=1em]60

[size=1em]61

[size=1em]62

[size=1em][size=1em]//给定一个单链表的头指针和一个指定节点的指针，在O(1)时间删除该节点
[size=1em]void DeleteNode(NodeL* head,NodeL* delNode)
[size=1em]{
[size=1em] if (!head || !delNode)
[size=1em] {
[size=1em]       return;
[size=1em] }

[size=1em] if (delNode->next!=NULL)//删除中间节点
[size=1em] {
[size=1em]       NodeL* next=delNode->next;
[size=1em]       delNode->next=next->next;
[size=1em]       delNode->value=next->value;
[size=1em]       delete next;
[size=1em]       next=NULL;
[size=1em] }else if (head==delNode)//删除头结点
[size=1em] {
[size=1em]       delete delNode;
[size=1em]       delNode=NULL;
[size=1em]       *head=NULL;
[size=1em] }else//删除尾节点，考虑到delNode不在head所在的链表上的情况
[size=1em] {
[size=1em]       NodeL* tmpNode=head;
[size=1em]       while (tmpNode && tmpNode->next!=delNode)
[size=1em]       {
[size=1em]          tmpNode=tmpNode->next;
[size=1em]       }
[size=1em]       if (tmpNode!=NULL)
[size=1em]       {
[size=1em]          delete delNode;
[size=1em]          delNode=NULL;
[size=1em]          tmpNode->next=NULL;
[size=1em]       }
[size=1em] }
[size=1em]}

[size=1em]void DeleteNodeTest()
[size=1em]{
[size=1em] int nodeCount=10;
[size=1em] for (int K=0;K<nodeCount;K++)
[size=1em] {
[size=1em]       NodeL* head=NULL;
[size=1em]       NodeL* cur=NULL;
[size=1em]       NodeL* delNode=NULL;
[size=1em]       for (int i=0;i<nodeCount;i++)
[size=1em]       {
[size=1em]          NodeL* tmpNode=new NodeL(i);
[size=1em]          if (i==0)
[size=1em]          {
[size=1em]             cur=head=tmpNode;
[size=1em]          }else{
[size=1em]             cur->next=tmpNode;
[size=1em]             cur=tmpNode;
[size=1em]          }
[size=1em]          if (i==K)
[size=1em]          {
[size=1em]             delNode=tmpNode;
[size=1em]          }
[size=1em]       }
[size=1em]       DeleteNode(head,delNode) ;
[size=1em] }
[size=1em]}
[size=1em]

　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();
}
}

cable5881 · 发表于 2014-8-11 17:30:58

谢谢楼主分享！！！！！！！！！！

fatherman · 发表于 2014-8-12 15:10:41

我只是路过打酱油的。

账号		自动登录	找回密码
密码			立即注册

[技术交流] 15道简单算法题(附源代码第二部分)

马上注册，结交更多好友，享用更多功能^_^