Remove Duplicates from Sorted List I II -- leetcode

(1) Remove Duplicates from Sorted List I
题目意思: 删除重复节点，但是保留第一个重复的结点.
For example,
Given 1->2->3->3->4->4->5, return 1->2->3->4->5.
Given 1->1->1->2->3, return 1->2->3.

思路:
(1) 定义两个指针,一个指向当前结点,一个指向其前驱
(2) 判断当前结点是否与其前驱结点值一样,一样则向后移动当前结点, 直到不在重复为止.
(3)此时当前结点可能为空, 删除重复结点后,前一个指针的next设为null即可;
(4)如果移动后,当前结点不为空,需要将前一个指针的next指向p(无论上一次p是否移动过, 没有移动即没有重复结点的情况下,前一个结点本来就是其前继结点,如果移动,那么p指向的正好是第一个不同于其前继的结点)
代码:

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == NULL) return NULL;
        ListNode *pre = head;//前驱结点
        ListNode *p = head -> next;
        while (p != NULL){
            while (p != NULL && pre -> val == p -> val){//前后结点值相同,移动p
                p = p -> next;
            }
            if (p == NULL) pre -> next = NULL;
            else {
                pre -> next = p;
                pre = p;
                p = p -> next;
            }

        }
        return head;
    }
};

2 Remove Duplicates from Sorted List II – leetcode
题目意思:删除重复节点，不保留任何重复结点.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

思路:(与上一题不同,要求同时将重复的结点删除)
(1)首先给原链表定义一个不重复的头结点;
(2)定义两个指针,其中一个始终指向不重复的结点(初始化的时候指向我们定义头结点),一个指向当前结点
(3)依次比较当前结点与其后一个结点是否重复,重复则当前指针向后移动
(4)判断当前结点的指针是否是第一个指针的后继,
1)如果是,表示当前结点不重复,然后前一个和后一个指针依次向后移动一次.
2)如果不是,表示后一个指针指向的结点重复, 移动后, 后一个指针指向的正是重复结点的最后一个,因此将前一个指针(始终指向不重复结点的指针)的后继指向后一个指针的后继,然后让后一个指针成为新链表中前一个指针的后继

代码:

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        //链表为空的情况
    if (pHead==NULL) return NULL;
        //定义一个不重复的头结点
        ListNode *newList = new ListNode(-1);
        newList -> next = pHead;
        //下面的情况头结点不重复
        ListNode *pre = newList;//前一个指针,始终指向链表中不重复的结点
        ListNode *p = pre-> next;

        while(p!=NULL){
            //p的下一个结点和p重复,则向后移动p
            while (p -> next != NULL && p -> next -> val == p -> val){ 
                p = p -> next;
            }
            //pre的后继结点不是p,证明p向后移动过,即有重复的结点,移动后的 p 指向的是重复结点的最后一位
            if (pre -> next != p){//有重复的情况
                pre -> next = p -> next;//将重复的所有结点删除
                p = pre -> next;
            }else {//没有重复的情况(两个指针同时向后移动一次)
                pre = p;
                p = p -> next;
            }
        }
        return newList->next;
    }
};