1. 题目描述

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Example 1:

Input: 1->2->3->3->4->4->5
Output: 1->2->5

Example 2:

Input: 1->1->1->2->3
Output: 2->3

2. 初解

两个指针,一前一后,curr=prev->next,然后现在两个指针一起往后走,每走一次就判断一下curr->val是否等于curr->next->val,如果相等说明出现了重复元素,用一个tmp指针向后遍历找出所有重复的元素,然后直接让curr等于第一个不重复元素就ok。

3. 代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* deleteDuplicates(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }

    struct ListNode* dummyHead =
        (struct ListNode *)malloc(sizeof(struct ListNode));
    dummyHead->val = 0;
    dummyHead->next = head;

    struct ListNode* prev = dummyHead;
    struct ListNode* curr = head;
    struct ListNode* tmp;

    while (curr != NULL) {
        if (curr->next != NULL && curr->next->val == curr->val) {
            tmp = curr->next;
            while (tmp->next != NULL && tmp->next->val == curr->val)
                tmp = tmp->next;
            curr = tmp->next;
            prev->next = curr;
        }
        else {
            curr = curr->next;
            prev = prev->next;
        }
    }

    return dummyHead->next;
}

struct ListNode* CreatLL(int* arr, int size) {
    struct ListNode* dummyHead =
        (struct ListNode *)malloc(sizeof(struct ListNode));
    dummyHead->val = 0;
    dummyHead->next = NULL;
    struct ListNode* ptr = dummyHead;
    struct ListNode* tmp;

    for (int i = 0; i < size; i++) {
        tmp = (struct ListNode *)malloc(sizeof(struct ListNode));
        tmp->next = NULL;
        tmp->val = arr[i];
        ptr->next = tmp;
        ptr = ptr->next;
    }

    return dummyHead->next;
}

void printLL(struct ListNode* head) {
    struct ListNode* ptr = head;
    while (ptr) {
        printf("%d -> ", ptr->val);
        ptr = ptr->next;
    }
    putchar('\n');
}

int main() {
    int arr[] = { 1, 1 };
    struct ListNode* head = CreatLL(arr, 2);
    printLL(head);
    head = deleteDuplicates(head);
    printLL(head);

    system("pause");
    return 0;
}
Last modification:September 8th, 2019 at 08:26 pm