leetcode-83.删除排序链表中的重复元素

Points

  • 链表

题意

给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。

示例 1:

输入: 1->1->2
输出: 1->2

示例 2:

输入: 1->1->2->3->3
输出: 1->2->3

示例 3:

输入: []
输出: []

示例 4:

输入: [1]
输出: [1]

算法

双指针(n2 = n1->next)遍历排序链表

如果两指针值相等,删除后一节点。

(注意判断n2是否越界!!!)

code

 1 /*
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* deleteDuplicates(ListNode* head) {
12         if(head == NULL)//链表为空,直接返回
13             return head;
14 ListNode *p = head, *nextp; 15 if(head->next != NULL) 16 nextp = head->next; 17 else //只有一个元素,直接返回 18 return head;
19 while(nextp != NULL)//遍历链表 20 { 21 if(nextp->val == p->val)//出现重复 22 { 23 p->next = nextp->next;//删除重复节点 24 delete nextp; 25 nextp = p->next; 26 } 27 else 28 { 29 if(nextp->next == NULL)//边界判断 30 break; 31 nextp = nextp->next; 32 p = p->next; 33 } 34 } 35 return head; 36 } 37 };