• 关键字:链表操作
  • 难度:简单
  • 前置知识:链表
  • 题目大意:在一个有序的单向链表当中,删除所有重复的数

题目描述

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.

解法

这道题目呢~是一道非常简单的链表操作题目!

首先,我们可以根据“有序”的条件知道,所有相同的数,在链表中,都是相邻的(不然怎么叫“有序”!),在有了这个条件之后,我们就只需要简单的进行这样的处理:将连续的一段相同的数只保留一个!

或者说,对于一个数,如果它的后继结点与它相同,那么就删除它的后继结点,而在对整个链表都进行一次遍历并对每个结点都这样处理之后,我们就可以得到一个没有重复数的链表了!

参考代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode *ptr = head;
        // 依次遍历整个链表
        while (ptr) {
            // 删除之后与当前结点相同的结点
            while (ptr -> next && ptr -> val == ptr -> next -> val) ptr -> next = ptr -> next -> next;
            // 继续遍历下个结点
            ptr = ptr -> next;
        }
        return head;
    }
};

登录发表评论 注册

反馈意见