单链表的基础知识

单链表的基础知识主要包括链表节点的删除、链表节点的插入、链表的排序、链表的逆置、寻找链表的中间节点、寻找链表的倒数第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<n;j++)
15         {
16             p=head;
17             for (int i=0;i<n-j;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 }

寻找但链表中倒数第m个节点

方法一：首先求出单链表总的长度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<n-m;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<m;i++)
11     {
12         p2=p2->next;
13     }
14     while(p2)
15     {
16         p2=p2->next;
17         p1=p1->next;
18     }
19     return p1;
20 }