LeetCode之Remove Duplicates from Sorted List

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