数据结构——链表

发布时间：2023年12月30日

1.可以通过记录最后一个节点来判断是否相交

while(pa->next)

{

????pa = pa-next;

}?

while(pb->next)

{

????pb= pb->next;

}

if(pa == pb){...}

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

基本原理，讲当前结点的下个一个结点的数据赋值给当前结点，然后释放下一个结点。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

typedef?struct?node

{

????int?value;

????struct?node *next;

} list_node;

void?test(list_node* pCur)

{

????list_node *pNext = pCur->next;

????if?(pNext)

????{

????????pCur->next = pNext->next;

????????pCur->value = pNext->value;

????}

????delete?pNext;

}

3.给定一个结点指针，在结点之前插入一个结点，解法同上

先后插一个结点，然后交换当前结点和后面结点的数据。?

4.判断单链表是否有环

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

typedef?struct?node

{

????int?value;

????struct?node *next;

} list_node;

int???is_link_list_cicled(list_node*?? head)?????

{?????

????list_node *p = head,??

????list_node *q = head;?????

????while(p && q)?????

????{?????????????????????????

????????p =? p-> next;?????

????????q =? q-> next;?????

????????if(!q)?????

????????????return?0;?????

????????q = q-> next;???????

????????if(!q)?????

????????????return?0;?

?????????if(p?? ==?? q)?????

????????????return???1;??

????}

}

?5.找到环的入口点

公式x = （n-1）y + y -d;

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

typedef?struct?node

{

????int?value;

????struct?node *next;

} list_node;

int???is_link_list_cicled(list_node*?? head)?????

{?????

????list_node *slow = head,??

????list_node *fast = head;?????

????while(slow && fast)?????

????{?????????????????????????

????????slow =? slow-> next;?????

????????fast =? fast-> next;?????

????????if(!fast)?????

????????????return?0;?????

????????fast = fast-> next;?????

????????if(!fast)?????

????????????return?0;?

?????????if(slow?? ==?? fast)?????

????????????return???break;??

????}

//找到换的入口点

????while(slow != fast)

????{

????????slow = slow->next;

????????fast = fast->next;

????}

}

6.找出倒数第k个数

原理：使用两个指针相差k-1，当第一个指针指向最后的时候，第二个指针则指向第K个位置

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

list_node*?? findK(list_node*?? head,int?k)?????

{?????

????list_node* pAhead = head->next;

????list_node* pbehind = head->next;

????for?(int?i = 0;i < k ;++i)

????{

????????pAhead = pAhead->next;

????}

????while(pAhead->next)

????{

????????pAhead = pAhead->next;

????????pbehind = pbehind->next;

????}

????return?pAhead;

}

7.若结点个数为奇数则返回中间结点

若为偶数则返回中间第一个个结点

while(p->next && p->next->next)

{

??q = q->next;

??p = p->next->next;

}

return?q;

?8.带头结点的链表转置

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

list_node*?? findK(list_node*?? head)?????

{?????

????list_node* pPrev =NULL;

????list_node* pCur = head->next;

????list_node* pNext = NULL;

????while(pCur)

????{

????????pNext = pCur;

????????pCur->next = pPrev;

????????pPrev = pCur;

????????pCur = pNext;

????}

????head->next = pPrev;

????return?NULL;

}

9.找出相交链表的交点

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

list_node*?? findK(list_node*?? heada,list_node *headb)?????

{?

????list_node *p = heada->next;

????list_node *q = headb->next;

????int?pLen = 0;

????int?qLen = 0;

????int?steps =?abs(pLen -qLen);

????list_node *head = pLen > qLen? p:q;

????while(steps)

????{

????????head = head->next;

????????steps--;

????}

????pLen>qLen?p = head:q=head;

????while(p!=q)

????{

????????p = p->next;

????????q = q->next;

????}

????return?NULL;

}

文章来源:https://blog.csdn.net/x20020402/article/details/124456588
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
最新文章