正文
① 删除有序链表中重复的元素-I
描述（题目简单） 考点：链表
删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次
例如：
给出的链表为1-> 1-> 2，返回1 ->2
给出的链表为1→1→2→3→3,返回1→2→3.
解题思路：
根据题意，我们分析，要删除有序链表当中重复的元素使所有重复元素只出现一次，在这个过程当中，可以选定两个链表指针i和j，通过设定i为head，j为i.next，依次通过循环将重复元素的个数减为0，如果没有发现重复的元素，令j = j.next，再次进行判断；如果发现有重复元素，令i.next = j.next，除掉重复元素，依次递归进行判断。
题解：
// 语言①：c struct ListNode* deleteDuplicates(struct ListNode* head) { if (head == NULL) { return head; } struct ListNode* p = head; while (p->next != NULL) { if (p->val == p->next->val) { //相邻数据相等时 p->next = p->next->next;//相等的数据的第一个的指针指向不相等的数据元素 } else { p = p->next; } } return head; }
//
//语言②：JavaScript /* 遍历链表，比较当前与下一个的值是否相等，如相等，把当前的下一个指向下一个的下一个。这里有两点要注意：1.要判断next以及next.next是否存在；2.只有值不相等遍历指针才往下走。 */ function deleteDuplicates(head) { // write code here let current = head; while (current) { if (current.next && current.val == current.next.val) { if (current.next.next) { current.next = current.next.next; } else { current.next = null; } } else { current = current.next; } } return head; } module.exports = { deleteDuplicates: deleteDuplicates, };
② 删除有序链表中重复的元素-II
描述（题目较难） 考点：链表
给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
例如：
给出的链表为1→2→3→3→4→4→5, 返回1→2→5.
给出的链表为1→1→1→2→3, 返回2→3.
数据范围：链表长度 100000≤n≤10000，链表中的值满足 |val| ≤1000
要求：空间复杂度 O(n)，时间复杂度 O(n)
进阶：空间复杂度 O(1)，时间复杂度 O(n)
解题思路：
可以利用双指针法，首先我们可以设置一个newhead对象，pre = newhead，cur = head，在已知head的情况下，我们开始循环判断cur对象，设置循环条件为cur ->next不为空，判断cur->val是否等于cur->next->val，如果等于就将count的值累加（其中count的值为链表中的重复累加元素的个数和），当有重复的情况发生，就令pre->next = cur->next，count = 0，删除该元素，始终进行如下判断，如果没有重复，就将pre链表的值变为现在cur链表的值，递归条件为cur = cur - next。
1.首先加上一个空的头结点，便于处理删除第一个结点的情况。
2.需要设一个pre指针跟踪工作结点及记录一路留下来的结点。
3.用2个指针p,q来比较结点值是否相同。
4.不同时，pre指向p，p指向q，q指向q->next。
5.相同时，继续看q的后面是否还有一样，直到找到不同的，或者到链尾。
a,若后面还有不同的，则更换pre,p,q指针的指向，继续比较。
b,若q值后面一直到链尾没有不同的，那么从p到q都要删掉，pre指空完结。
题解：
//语言① ：c struct ListNode* deleteDuplicates(struct ListNode* head ) { struct ListNode* L =(struct ListNode*)malloc(sizeof(struct ListNode)); //新建结点 L->next = head; //指针域置空 if(head == NULL || head->next == NULL) return head; //0个或1个元素时不会有重复的元素，原样返回即可 struct ListNode* pre = L; //前驱指针 struct ListNode* p = head; struct ListNode* q = head->next; while(q != NULL){ if(q->val != p->val){ //不同值时均后移 pre = p; p = q; q = q->next; } else{ while(q->next->val == q->val && q->next != NULL) q = q->next; //后面还有相同值时继续后移 if(q->next == NULL){ //竟然一直移到了末尾 pre->next = NULL; //从p到q全部不要 return L->next; //提前返回 } p = q->next; //略过重复元素，重新开始比较 pre->next = p; //前驱也要同步跟上 q = p->next; } } return L->next; }
// 语言②：JavaScript function deleteDuplicates(head) { // write code here if (head == null) return head; const dummyNode = new ListNode(-1); dummyNode.next = head; let cur = dummyNode; while (cur.next && cur.next.next) { if (cur.next.val === cur.next.next.val) { const temp = cur.next.val; while (cur.next && cur.next.val === temp) { cur.next = cur.next.next; } } else { cur = cur.next; } } return dummyNode.next; }
