本文共 2483 字，大约阅读时间需要 8 分钟。

概述

83 . 题目

Given a sorted linked list, delete all duplicates such that each element appear only once.

Example 1:

Input: 1->1->2

Example 2:

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

• 和去掉数组中的重复元素差不多，链表去除重复结点，可以采取思路，当遍历到某一结点n，那么接下来继续遍历，只要一样就继续遍历，最后将n之后的重复的元素一下子删除掉。
  这个比较简单：

/** * 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* temp = head;        ListNode* point = head;          while(temp)        {             while(point != nullptr && point->val == temp->val)             {                 point = point->next;             }             temp->next = point;             temp = point;        }               return head;    }};

• 关键点 一： 要想到用一个结点 记录当前结点，另一个结点开始遍历和当前结点比较，直到和当前结点不一样的结点为止：
• 最后 将中间的部分删除： temp->next = point;
• 将当前结点 更新： temp = point;

82. Remove Duplicates from Sorted List II

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

Example 2:

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

和第一道不同的是，这里要删掉所有的重复项，由于链表开头可能会有重复项，被删掉的话头指针会改变，而最终却还需要返回链表的头指针。

• 所以需要定义一个新的节点，然后链上原链表，然后定义一个前驱指针和一个现指针，每当前驱指针指向新建的节点，现指针从下一个位置开始往下遍历，遇到相同的则继续往下，直到遇到不同项时，把前驱指针的next指向下面那个不同的元素。如果现指针遍历的第一个元素就不相同，则把前驱指针向下移一位。
• 代码：

/** * 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) {               if(!head || !head->next)  return head;                ListNode* start = new ListNode(0);        start->next = head;        ListNode* pre = start;        while(pre->next)        {            ListNode* cur = pre->next;            while(cur->next && cur->next->val == cur->val)            {                cur = cur->next;            }            if(cur != pre->next)            {                pre->next = cur->next;            }            else            {                pre = pre->next;            }        }        return start->next;    }};

• 代码分析

1. 指定一个新的结点作为头结点的前驱：
   ListNode* start = new ListNode(0);
   start->next = head;
   ListNode* pre = start;
2. 开始遍历，cur 指针开始指向头结点，如果cur结点和下一个结点不一样，那么cur结点就是一个单独的结点，此时只需要将前驱结点向下移动一步即可。如果cur结点和下一个结点一样，继续遍历，直到不一样为止，此时cur ！= pre->next。 则需要将前驱结点的后驱指向cur结点的后驱： pre->next = cur->next;
3. 可以在纸上模拟一下这样记忆会更加深刻！

转载地址：http://vuzjn.baihongyu.com/