作者：手机用户2502879933 | 来源：互联网 | 2023-01-28 13:04
单链表的基础知识主要包括链表节点的删除、链表节点的插入、链表的排序、链表的逆置、寻找链表的中间节点、寻找链表的倒数第m个节点，本文主要是用代码对这些基础问题进行了实
单链表的基础知识主要包括链表节点的删除、链表节点的插入、链表的排序、链表的逆置、寻找链表的中间节点、寻找链表的倒数第m个节点，本文主要是用代码对这些基础问题进行了实现。
typedef struct node{
int data;
node *next;
}node;
1 node *remove(node *head,const int &target)
2 {
3 node *p1,*p2;
4 p1=head;
5 while (p1->data!=target && p1->next!=NULL)
6 {
7 p2=p1;
8 p1=p1->next;
9 }
10 if (target==p1->data)
11 {
12 if (p1==head)
13 {
14 head=p1->next;
15 free(p1);
16 }
17 else
18 {
19 p2->next=p1->next;
20 free(p1);
21 }
22 }
23 else
24 {
25 cout<<"The list dosen't include the target."<<endl;
26 }
27
28 return head;
29
30 }
1 node *insertNoHead(const node *head,node *prevoiusPtr,const int &target)
2 {
3 node *insertPtr;
4 insertPtr=new node;
5 insertPtr->data=target;
6 insertPtr->next=prevoiusPtr->next;
7 prevoiusPtr->next=insertPtr;
8 return head;
9 }
10
11 node *insertHead(node *&head,const int &target)
12 {
13 node *insertPtr;
14 insertPtr=new node;
15 insertPtr->next=head;
16 head=insertPtr;
17 return head;
18 }
1 node *sort(node *head)
2 {
3 node *p,*p1,*p2;
4 int n;
5 int temp;
6 n=length(head);
7 if (head==NULL || head->next==NULL)
8 {
9 return head;
10 }
11 else
12 {
13 p=head;
14 for (int j=1;j)
15 {
16 p=head;
17 for (int i=0;i)
18 {
19 if (p->data>p->next->data)
20 {
21 temp=p->data;
22 p->data=p->next->data;
23 p->next->data=temp;
24 }
25 p=p->next;
26 }
27 }
28 return head;
29 }
30
31 }
1 int length(node *head)
2 {
3 int sum=0;
4 while(head)
5 {
6 sum++;
7 head=head->next;
8 }
9 return sum;
10
11 }
1 node *reverse(node *head)
2 {
3 node *p1,*p2,*p3;
4 if (head==NULL || head->next==NULL)
5 {
6 return head;
7 }
8 else
9 {
10 p1=head;
11 p2=p1->next;
12 while(p2)
13 {
14 p3=p2->next;
15 p2->next=p1;
16 p1=p2;
17 p2=p3;
18
19 }
20 head->next=NULL;
21 head=p1;
22 return head;
23 }
24 }
首先设置两个指针p1和p2都指向头指针，然后p1指针一次走一步，p2指针一次走两步，当p2走到单链表的末尾时，此时p1所指向的节点即为中间节点。
1 node *searchMiddle(node *head)
2 {
3 node *p1,*p2;
4 p1=p2=head;
5 int n=length(head);
6 if(n<3)
7 {
8 return head;
9 }
10 else
11 {
12 while(p2->next && p2->next->next)
13 {
14 p2=p2->next->next;
15 p1=p1->next;
16
17 }
18 return p1;
19 }
20 }
方法一：首先求出单链表总的长度n，然后从链表的头节点开始遍历，当遍历到n-m个节点时，即为链表中倒数第m个节点。
node *FindReverseM1(node *head,int m)
{
node *p;
int n=length(head);
if (n==0 || m>n)
{
return NULL;
}
p=head;
for(int i=0;i)
{
p=p->next;
}
return p;
}
方法二：首先设置两个指针p1和p2，同时指向单链表的头节点，然后用p2遍历链表，将p2指向链表中第m个节点，接着将p1和p2同时进行遍历，当p2指向链表中末尾节点时，p1所指向的节点即为倒数第m个节点。
1 node *FindReverseM2(node *head,int m)
2 {
3 node *p1,*p2;
4 int n=length(head);
5 if (n==0 || n<m)
6 {
7 return NULL;
8 }
9 p1=p2=head;
10 for (int i=0;i)
11 {
12 p2=p2->next;
13 }
14 while(p2)
15 {
16 p2=p2->next;
17 p1=p1->next;
18 }
19 return p1;
20 }
京公网安备 11010802041100号