• 发表于 3年前
• 阅读 28
• 收藏 1
• 评论 0

1. void List::reverse()
2. {
3.         list_node * p = head;
4.         list_node * q = p->next;
5.         list_node * r = NULL;
6.         while(q){
7.                 r = q->next;
8.                 q->next = p;
9.                 p = q;
10.                 q = r;
11.         }
14. }

1. void List::reverse2(list_node * curnode)
2. {
4.         if(curnode->next==NULL)
5.         {
6.                 cur = curnode;
7.                 return;
8.         }
9.
10.         reverse2(curnode->next);
11.         curnode->next->next=curnode;
13.         {
15.                 cur = curnode;
16.                 cur->next = NULL;
17.         }
18. }

1. void List::merge(List & list)
2. {
3.         list_node * a = head;
4.         list_node * b = list.head;
5.         list_node * tempa= a;
6.         list_node * tempb = b;
7.         while(a&&b)
8.         {
9.                 if(a->value <= b->value)
10.                 {
11.                         while(a&&b&&a->value <= b->value)
12.                         {
13.                                 tempa = a;
14.                                 a = a->next;
15.                         }
16.                         tempa->next=b;
17.                 }
18.                 else
19.                 {
20.                         while(a&&b&&a->value > b->value)
21.                         {
22.                                 tempb = b;
23.                                 b = b->next;
24.                         }
25.                         tempb->next=a;
26.                 }
27.
28.         }
29. }

1. list_node* List::recursive_merge(list_node * a,list_node * b)
2. {
3.         if(a == NULL)return b;
4.         if(b == NULL)return a;
5.         if(a->value <= b->value){
6.                 a->next=recursive_merge(a->next,b);
7.                 return a;
8.         }
9.         if(a->value > b->value)
10.         {
11.                 b->next=recursive_merge(a,b->next);
12.                 return b;
13.         }
14. }

3.有一个链表L,其每个节点有2个指针，一个指针next指向链表的下个节点，另一个random随机指向链表中的任一个节点，可能是自己或者为空，写一个程序，要求复制这个链表的结构并分析其复杂性

1. List List::copyRndList()
2. {
3.         list_node * newhead = NULL;
4.         list_node * newcur = NULL;
5.         list_node * cur = head;
6.         while(cur)
7.         {
13.                 }
14.                 else{
15.                         newcur = new list_node;
16.                         newcur->value = cur->value;
17.                         newcur->next = cur->next;
18.                         cur->next = newcur;
19.                 }
20.                 cur=cur->next->next;
21.         }
23.         while(cur){
24.                 if(cur->rnd)
25.                         cur->next->rnd=cur->rnd->next;
26.                 else
27.                         cur->next->rnd = NULL;
28.                 cur = cur->next->next;
29.         }
31.         list_node * dst = cur->next;
32.         while(cur)
33.         {
34.                 list_node * temp = dst->next;
35.                 cur->next = temp;
36.                 if(temp)dst->next = temp->next;
37.                 cur = cur->next;
38.                 dst=dst->next;
39.         }
40.         List newList;
42.         return newList;
43. }

4. 找出单向链表中中间结点

1. list_node * List::middleElement()
2. {
3.         list_node * p = head;
4.         list_node * q = head->next;
5.         while(q){
6.                 p = p->next;
7.                 if(q)q=q->next;
8.                 if(q)q=q->next;
9.         }
10. }

5. 如何检查一个单向链表上是否有环

1. list_node * List::getJoinPointer()
2. {
3.
5.         list_node * one = head;
6.         list_node * two = head->next;
7.         while(one != two){
8.                 one = one->next;
9.                 if(two)two=two->next;
10.                 else break;
11.                 if(two)two=two->next;
12.                 else break;
13.         }
14.         if(one == NULL || two == NULL)return NULL;
15.         return one;
16. }

1. list_node * List::findCycleEntry()
2. {
3.         if(checkCycle()==false)return NULL;
4.         list_node * joinPointer = getJoinPointer();
5.         list_node * p = head;
6.         list_node * q = joinPointer->next;
7.         while(p!=q)
8.         {
9.                 p=p->next;
10.                 q=q->next;
11.         }
12.         return p;
13. }

7.只给定单链表中某个结点p(并非最后一个结点，即p->next!=NULL)指针，删除该结点。

1. void List::deleteByPointer(list_node * node)
2. {
3.         if(node)
4.         {
5.                 if(node->next){
6.                         node->value = node->next->value;
7.                         node->next = node->next->next;
8.                 }
9.         }
10. }

8.在p前面插入一个节点

9.给定单链表头结点，删除链表中倒数第k个结点

1. list_node * List::lastKelement(int k){
2.         int t = k;
3.         list_node * p = head;
4.         while(p&&t){
5.                 p=p->next;
6.                 t--;
7.         }
8.         if(p == NULL && t >0)return NULL;
10.         while(q && p){
11.                 p=p->next;
12.                 q=q->next;
13.         }
14.         return q;
15. }

10. 判断两个链表是否相交。

1. bool List::isIntersecting(const List & list)
2. {
3.         bool flag = false;
4.         if(this->checkCycle())
5.         {
6.                 list_node * p = getJoinPointer();
7.                 list_node * q = list.head;
8.                 while(q){
9.                         if(q == p){
10.                                 flag = true;
11.                                 break;
12.                         }
13.                         q=q->next;
14.                 }
15.                 flag = true;
16.         }
17.         else
18.         {
19.                 list_node * p = head;
20.                 list_node * q = list.head;
21.                 while(p->next)p=p->next;
22.                 while(q->next)q=q->next;
23.                 if(p  == q)flag = true;
24.                 else flag =false;
25.         }
26.         return flag;
27. }

11. 两个链表相交，找出交点

1. list_node * List::intersectNode(const List & list)
2. {
3.         if(!isIntersecting(list))return NULL;
4.         int a = cnt;
5.         int b = list.cnt;
6.         list_node * p;
7.         list_node * q;
10.         a = abs(cnt - list.cnt);
11.         while(p && a)
12.         {
13.                 p = p->next;
14.                 a--;
15.         }
16.         while(p&&q)
17.         {
18.                 if(q==p)break;
19.                 p=p->next;
20.                 q=q->next;
21.         }
22.         if(p && q && p == q)return p;
23.         return NULL;

×