struct ListNode{
    int val(x);
    ListNode*next;
    ListNode(x):
        val(x),next(NULL){}
};
class Solution{
public:
    ListNode* delecttheaimlastnode(ListNode*phead,int target){
        if(phead==NULL){
            return NULL;
        }
        ListNode*pnode=phead;
        int i=0;
        while(pnode!=NULL){
            if(pnode->val==target){
                i++;
            }
            pnode=pnode->next;//找指定元素出现次数
        }
        if(i==0){//0次就返回
            return head;
        }
        if(i==1){
            while(pnode!=NULL){
                if(pnode->next->val==target){
                    pnode->next==pnode->next->next;
                    return phead;
                }
                else{
                    pnode=pnode->next;
                }
            }
            
        }
        while(pnode!=NULL){
            if(pnode->val==target){
                while(pnode->next->next==target&&pnode->next==target){
                    pnode=pnode->next;
                    
                }
                pnode->next=pnode->next->next;
            }
            else{
                pnode=pnode->next;
            }
        }
        return phead;
    }
};

    
 


数据结构实验之链表七：单链表中重复元素的删除

Time Limit: 1000MS Memory limit: 65536K

题目描述
按照数据输入的相反顺序（逆位序）建立一个单链表，并将单链表中重复的元素删除（值相同的元素只保留最后输入的一个）。
输入
第一行输入元素个数n； 
第二行输入n个整数。
输出
第一行输出初始链表元素个数； 
第二行输出按照逆位序所建立的初始链表；
第三行输出删除重复元素后的单链表元素个数；
第四行输出删除重复元素后的单链表。
示例输入

10
21 30 14 55 32 63 11 30 55 30

示例输出

10
30 55 30 11 63 32 55 14 30 21
7
30 55 11 63 32 14 21


 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 struct vode
 4 {
 5     int date;
 6     struct vode *next;
 7 };
 8 int main()
 9 {
10     struct vode *head,*p,*q,*p1;
11     head=(struct vode *)malloc(sizeof(struct vode ));
12     head->next=NULL;
13     int n,i;
14     scanf("%d",&n);
15     for(i=1;i<=n;i++)
16     {
17         p=(struct vode *)malloc(sizeof(struct vode ));
18         p->next=NULL;
19         scanf("%d",&p->date);
20         p->next=head->next;
21         head->next=p;
22     }
23     printf("%d\n",n);
24     p=head->next;
25     int k=0;
26     while(p)
27     {
28         if(k==0)
29         {
30             printf("%d",p->date);
31             k=1;
32         }
33         else printf(" %d",p->date);
34         p=p->next;
35     }
36     printf("\n");
37     p=head->next;
38     int sum=0;
39     while(p)
40     {
41         p1=p;
42         q=p1->next;
43         while(q)
44         {
45             if(p->date==q->date)
46             {
47                 q=q->next;
48                 p1->next=q;
49                 sum++;
50             }
51             else
52             {
53                 p1=p1->next;
54                 q=q->next;
55             }
56         }
57         p=p->next;
58     }
59     printf("%d\n",n-sum);
60     p=head->next;
61      k=0;
62     while(p)
63     {
64         if(k==0)
65         {
66             printf("%d",p->date);
67             k=1;
68         }
69         else printf(" %d",p->date);
70         p=p->next;
71     }
72     printf("\n");
73     return 0;
74 }

View Code 
 



转载于:https://www.cnblogs.com/kuangdaoyizhimei/p/3264603.html

[题目]：    给定一个单向链表（长度未知），请设计一个既节省时间又节省空间的算法来找出该链表中的倒数第m个元素。实现这个算法，并为可能出现的特例情况安排好处理措施。“倒数第m个元素”是这样规定的：当m=0时，链表的最后一个元素将被返回。
    
    如果沿从头至尾的方向从链表中的某个元素开始，遍历m个元素后刚好达到链表尾，那么该元素就是我们所要找的。这样，我们可以引出第一种办法：从头结点开始，依次对链表的每一个元素进行这样的测试，遍历m个元素，看是否到达链表尾。直到我们找到那个倒数第m个元素为止。很明显，这个方案的效率是很差的，因为我们将对同一批元素进行反复多次的遍历。仔细研究一下这个方案就会发现，对于链表中的大部分元素，我们都要遍历m个元素；如果这个链表的长度为n，这个算法的执行时间大概是O(mn)级的。我们应该尝试寻找一个优于O(mn)级的解决方案。

    如果我们首先遍历该链表，统计链表的长度（假定为n），那么要找的元素在该链表中的位置即n-m。这样，从链表的头开始，向后遍历n-m个元素即可。虽说整个过程需要对链表进行2次遍历，但它仍然是一个O(n)级的算法，而且它只需要很少的几个临时变量。相对于此前的方案，这一思路的时间和空间效率有了显著的改进。要是你能设法省下统计链表长度的那一次遍历，这个算法将更加有效了。

    首先不妨假设在前2种算法中我们用指针p1遍历链表。p1指向链表尾的时候，我们所要找的元素（假定为data-m)跟链表尾的相对距离为m。如果这时候有另外一个指针p2指向data-m，也就是说，p1与p2间隔m个元素。如果把该单向链表改为双向链表，并保持p1、p2之间的同步，当p2指针回溯到链表头结点的时候，p1指针刚好指向从头结点开始的第m个元素。根据这个相隔m个位置的相对距离，我们完全可以明确地再设置一个用来遍历单向链表的指针p2，让它与链表的第一个指针p1（前2种算法中用于统计链表长度的指针）间隔m个元素，然后让它们同步前进。当p1指向链表尾时，p2刚好指向倒数第m个元素。
    那么怎样才能让这2个指针保持正确的m间距呢？我们可以这样做：当p1从链表头开始统计链表元素个数（注意要从0开始计算），等数到第m个元素时，再让p2指针从链表头开始出发。这个，他们之间的距离就是m个元素了。
    在这一过程中，如果链表的长度不足m个元素，我们在试图使p1前进m个元素时，很可能就会在半路上遇见对“NULL”指针进行操作的情况。因此，我们需要在这2个指针的出发阶段检查p1指针是否已经到达了链表的尾端。
算法描述： element *FindMToLastElement (int head,int m)
                      {
                          element *p1,*p2;
                          int i;
                          p1 = head;
                          for(i=0;i<m;i++)
                              {  
                               if(p1->next)
                               p1 = p1->next;
                              else
                              return NULL;
                              }
                         p2 = head;
                         while(p1->next)
                           {
                            p1 = p1->next;
                            p2 = p2->next;
                           }
                        return p2;
                      }
            
C++实现：
/*show_MToLast_node.cpp     Amirural设计 */
#include <iostream.h>
class ListNode
{
private:
 int data;
 ListNode *next_node;
 static ListNode *now;                                                 //目前的结尾结点指针
 const static ListNode *head;                                    //连接链表的起始指针，head ->next_node指向第一个结点
public:
 ListNode(int node_data):data(node_data),next_node(NULL){}
 ListNode():next_node(NULL)
 {head=now=this;}
 static void add_node(int new_data);                      //增加新的结点
 static void show_all_node();                                   //显示所有的结点          
 static void show_MToLast_node(int m);              //显示倒数第m个结点
};
ListNode *ListNode::now;            
const ListNode *ListNode::head;
void ListNode::add_node(int new_data)
{
 now->next_node=new ListNode(new_data);
 now=now->next_node;
}
void ListNode::show_all_node()
{
 now=head->next_node;
 while(now!=NULL)
 {
 cout<<now->data;
 if(now->next_node!=NULL)
  cout<<"->";
 now=now->next_node;
 }
}
void ListNode::show_MToLast_node(int m)
{
        ListNode *index,*mBehind;
        int i;
        index = head->next_node;
        for(i=0;i<m;i++)
         {  
         if(index->next_node)
          index = index->next_node;
        }
        mBehind = head->next_node;
        while(index->next_node)
        {
          index = index->next_node;
          mBehind = mBehind->next_node;
        }
        cout<<"The m to last data is:"<<mBehind->data<<endl;
 }
void main()
{
 int data,m;
 char choice;
 ListNode startnode;                
 do{
  cout<<"Please input data:";
  cin>>data;
  startnode.add_node(data);   
        
  cout<<"Do you want to input another data?";
  cin>>choice;
 }while(choice=='y'||choice=='Y');
 ListNode::show_all_node();
 cout<<"/nPlease input m:";
 cin>>m;
 ListNode::show_MToLast_node(m);
}

数据结构实验之链表七：单链表中重复元素的删除
Problem Description

按照数据输入的相反顺序（逆位序）建立一个单链表，并将单链表中重复的元素删除（值相同的元素只保留最后输入的一个）。
Input		

第一行输入元素个数 n (1 <= n <= 15)；

第二行输入 n 个整数，保证在 int 范围内。
Output				

第一行输出初始链表元素个数；

第二行输出按照逆位序所建立的初始链表；

第三行输出删除重复元素后的单链表元素个数；

第四行输出删除重复元素后的单链表。
Sample Input

10

21 30 14 55 32 63 11 30 55 30
Sample Output				

10

30 55 30 11 63 32 55 14 30 21

7

30 55 11 63 32 14 21
第一个用for，第二个用while，不知道删除元素的时候为什么不能用tail->next来判断

我肥来了

当tail为NULL时，tail->next判断失效，while循环不能停下来，

也就是不能用一个只向空的指针来进行tail ->NULL的判断。
#include <stdio.h>
#include <stdlib.h>

struct node
{
    int data;
    struct node *next;
};
int main()
{
    int n,i;
    struct node *head,*tail,*p,*q;
    scanf("%d",&n);
    head=(struct node *)malloc(sizeof(struct node));
    head->next=NULL;
    for(i=1; i<=n; i++)
    {
        p=(struct node *)malloc(sizeof(struct node));
        scanf("%d",&p->data);
        p->next=head->next;
        head->next=p;
    }
    tail=head->next;
    printf("%d\n",n);
    while(tail)
    {
        if(tail->next==NULL)
            printf("%d\n",tail->data);
        else
            printf("%d ",tail->data);
        tail=tail->next;
    }
    for(tail=head->next; tail!=NULL; tail=tail->next)
    {
        p=tail;
        q=tail->next;
        while(q!=NULL)
        {
            if(q->data==tail->data)
            {
                p->next=q->next;
                free(q);
                q=p->next;
            }
            else
            {
                p=q;
                q=q->next;
            }
        }
    }
    int num=0;
    for(tail=head->next; tail!=NULL; tail=tail->next)
        num++;
    printf("%d\n",num);
    tail=head->next;
    while(tail)
    {
        if(tail->next==NULL)
            printf("%d\n",tail->data);
        else
            printf("%d ",tail->data);
        tail=tail->next;
    }
    return 0;
}

手动分割线
#include <stdio.h>
#include <stdlib.h>

struct node
{
    int data;
    struct node *next;
};
int main()
{
    int n,i;
    struct node *head,*tail,*p,*q;
    head=(struct node *)malloc(sizeof(struct node));
    head->next=NULL;
    scanf("%d",&n);
    for(i=1; i<=n; i++)
    {
        p=(struct node *)malloc(sizeof(struct node));
        scanf("%d",&p->data);
        p->next=head->next;
        head->next=p;
    }
    printf("%d\n",n);
    tail=head->next;
    while(tail)
    {
        if(tail->next==NULL)
            printf("%d\n",tail->data);
        else
            printf("%d ",tail->data);
        tail=tail->next;
    }
    tail=head->next;
    while(tail)
    {
        p=tail;
        q=tail->next;
        while(q!=NULL)
        {
            if(q->data==tail->data)
            {
                p->next=q->next;
                free(q);
                q=p->next;
                n--;
            }
            else
            {
                p=q;
                q=q->next;
            }
        }
        tail=tail->next;
    }
    printf("%d\n",n);
    tail=head->next;
    while(tail)
    {
        if(tail->next==NULL)
            printf("%d\n",tail->data);
        else
            printf("%d ",tail->data);
    tail=tail->next;
    }
    return 0;
}