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