Edward's Blog

---

title: 9.22数据结构上机——Polya四原则 date: 2019-09-22 21:21:13 tags: - 数据结构 - C ---# Remove Duplicates from Sorted List

Polya's Four-Step Problem-Solving Process

1. Understand the problem 理解问题

• 题目中给定一个有序（非降序）序列，序列中可能存在重复项，要求删除序列中存在的重复项。 例如： 对于序列1->1->2->3->3，1 存在 1 个重复项，3 存在 1 个重复项，任务是把 1 的重复项和 3 的重复项在序列中删掉，最后结果为1->2->3。

• 题目中序列以链表的形式给出，具体代码为

//Definition for singly-linked list.
struct ListNode {
    int val;
    struct ListNode *next;
};

2. Devising a Plan 构想方案 根据题目给出的链表定义，我们可以遍历整个链表，并将每个结点与后面的结点作比较；如果两结点值相同（即出现了重复项），就更改当前结点的next指针，++具体为将前面结点的 next 指针跳过下一个具有相同值的结点（待删除结点）而直接指向再下一个结点++。即采用

   p->next=p->next->next。

3. Carry out the plan 执行方案

struct ListNode* deleteDuplicates(struct ListNode* head){
    struct ListNode *L = head;
    while(L&&L->next){
        if(L->val==L->next->val)
            L->next=L->next->next;
        else
            L=L->next;
    }
     return head;
}

LeetCode 执行结果：

4. Look back 反思回顾 还可以使用递归的方式。