LeetCode之Remove Duplicates from Sorted List

举报
chenyu 发表于 2021/07/27 00:57:41 2021/07/27
1.6k+ 0 0
【摘要】 1、题目 Given a sorted linked list, delete all duplicates such that each element appear only once. For example, Given 1->1->2, return 1->2. Given 1->1-&gt...

1、题目

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

1->2->2->2 return 1->2

1->2->3->3 return 1->3


2、代码实现


       #include <stdio.h>
       #include <unistd.h>
       #include <stdlib.h>
       struct List_Node {
       	int val;
        struct List_Node *next;
       };
       struct List_Node* deleteDuplicates(struct List_Node* head) {
       }
       void show_list (struct List_Node* head) {
       	while (head != NULL) {
       		printf("val:%d\n", head->val);
       		head = head->next;
       	}
       }
       struct List_Node* create_head1(){
       	struct List_Node *p1, *p2, *p3, *p4, *p5;
       	p1 = (struct List_Node *)malloc(sizeof(p1));
       	p2 = (struct List_Node *)malloc(sizeof(p2));
       	p3 = (struct List_Node *)malloc(sizeof(p3));
       	p4 = (struct List_Node *)malloc(sizeof(p4));
       	p5 = (struct List_Node *)malloc(sizeof(p5));
       	p1->val = 1;
       	p2->val = 1;
       	p3->val = 2;
       	p4->val = 3;
       	p5->val = 3;
       	p1->next = p2;
       	p2->next = p3;
       	p3->next = p4;
       	p4->next = p5;
       	p5->next = NULL;
       	return p1;
       }
       struct List_Node* create_head2(){
       	struct List_Node *p1, *p2, *p3, *p4, *p5;
       	p1 = (struct List_Node *)malloc(sizeof(p1));
       	p2 = (struct List_Node *)malloc(sizeof(p2));
       	p3 = (struct List_Node *)malloc(sizeof(p3));
       	p4 = (struct List_Node *)malloc(sizeof(p4));
       	p5 = (struct List_Node *)malloc(sizeof(p5));
       	p1->val = 1;
       	p2->val = 2;
       	p3->val = 2;
       	p4->val = 2;
       	p5->val = 2;
       	p1->next = p2;
       	p2->next = p3;
       	p3->next = p4;
       	p4->next = p5;
       	p5->next = NULL;
       	return p1;
       }
       struct List_Node* create_head3(){
       	struct List_Node *p1, *p2, *p3, *p4, *p5;
       	p1 = (struct List_Node *)malloc(sizeof(p1));
       	p2 = (struct List_Node *)malloc(sizeof(p2));
       	p3 = (struct List_Node *)malloc(sizeof(p3));
       	p4 = (struct List_Node *)malloc(sizeof(p4));
       	p5 = (struct List_Node *)malloc(sizeof(p5));
       	p1->val = 1;
       	p2->val = 2;
       	p3->val = 3;
       	p4->val = 3;
       	p5->val = 3;
       	p1->next = p2;
       	p2->next = p3;
       	p3->next = p4;
       	p4->next = p5;
       	p5->next = NULL;
       	return p1;
       }
       int main()
       {
        struct List_Node *head = create_head3();
       	show_list(head);
       	puts("after");
       	struct List_Node *p = head;
       	struct List_Node *q = head->next;
       	while (q != NULL) {
       		if (p->val == q->val) {
       			p->next = q->next;
       		} else {
       			p = q; //注意这里已经是head = head.next
       	 // p = p.next;
       		}
       		q = q->next;
       	}
       	show_list(head);
        	return 0;
       }
   
  

 
 


3、总结

比如1->1->2->3->3
我们这样分析
第一:需要搞个指针从第二个元素往后移动和前面一个指针指向下一个元素对比,如果前后2个指针的值一样,那么前面的指针需要指向下一个元素的下一个元素
第二:每对比一步,需要第二个指针往后移动
第三:只有当前元素和下面一个元素的下面一个元素不相等,我们就把他们连接起来,也就是走head = head.next;
过程如下
1->1
1->2 (head = head.next)
1->2->3(head = head.next)
1->2->3->null 

文章来源: chenyu.blog.csdn.net,作者:chen.yu,版权归原作者所有,如需转载,请联系作者。

原文链接:chenyu.blog.csdn.net/article/details/66974159

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

作者其他文章

评论(0

抱歉,系统识别当前为高风险访问,暂不支持该操作

    全部回复

    上滑加载中

    设置昵称

    在此一键设置昵称,即可参与社区互动!

    *长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

    *长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。