题解 | #删除有序链表中重复的元素-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，除掉重复元素，依次递归进行判断。

实例分析：1→1→2→3→3

具体C++代码为：

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */
 
class Solution {
public:
    /**
     *
     * @param head ListNode类
     * @return ListNode类
     */
    ListNode* deleteDuplicates(ListNode* head) {
        // write code here
        if(head == NULL)
            return NULL;
        for(ListNode* i = head; i != NULL; i = i->next){//挨个进行比较
            for(ListNode *j = i->next; j != NULL; j = j->next){
                if(i->val == j->val)
                    i->next = j->next;//删除重复元素
            }
        }
        return head;
    }
};

因为采用暴力法进行分析，并且设定了两个for循环进行逐个判断，所以时间复杂度为O(N^2)，空间复杂度为O(1)。

我们也可以这样编写C++程序：

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */
 
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode * p = head;
        if (p == NULL){
            return head;
        }
        while (p->next != NULL){
            if (p->val == p->next->val){//关键步骤
                p->next = p->next->next;//删除结点
            }
            else{
                p = p->next;
            }
        }
        return head;
    }
};

解法二：

思路分析：因为是一个升序的链表，所以可以设定一个结点作为头节点保存最终的结果，即在最后返回的时候，返回该结点的next值即可，使用指针cur遍历链表，因为是升序，所以当遇到两个值不相等时，可以将p和cur直接移动到下一个结点接着遍历即可，当重复结点全部删除后，方可返回最终的链表值。

具体java代码如下所示：

import java.util.*;
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */
public class Solution {
    /**
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode deleteDuplicates(ListNode head) {
        ListNode node = new ListNode(-1); //创建一个头节点
        node.next = head;
        ListNode p= node;
        ListNode cur = head;
        while (cur!= null && cur.next != null) {//只要不为空，就继续
           if(cur.val != cur.next.val) {//两个值不等的话
               p = cur;
           }
            else {
                while (cur.next != null && cur.val == cur.next.val)//相等的话
                        cur = cur.next;
                        p.next = cur.next;
                    }
                    cur = cur.next;
                }
        return node.next;//因为有头结点
    }
}

只要cur链表不为空，就继续循环，所以其时间复杂度为O(N)，空间复杂度为O(N)。