LintCode 112.删除排序链表中的重复元素

思路
二重循环遍历每一种情况

外层循环控制每个节点的处理
内层循环是从这个节点的下一个节点开始的遍历判断，如果相同则删除

/**
 * Definition of singly-linked-list:
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param head: head is the head of the linked list
     * @return: head of linked list
     */
    ListNode * deleteDuplicates(ListNode * head) {
        // write your code here
        ListNode *p = head;
        ListNode *s = NULL;
        while(p != NULL)
        {
            s = p->next;
            while(s != NULL)
            {
                if(s->val == p->val)    //删除s节点
                {
                    p->next = s->next;
                    delete s;
                    s = p->next;
                }
                else
                {
                    s = s->next;
                }
                
            }
            p = p->next;
        }
        return head;
    }
};

思路简单，效率不高

附上参考答案

/**
* 本参考程序来自九章算法，由 @九章算法 提供。版权所有，转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班，
* - Big Data 项目实战班，算法面试高频题班, 动态规划专题班
* - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code
*/ 

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution{
public:
    /**
     * @param head: The first node of linked list.
     * @return: head node
     */
    ListNode *deleteDuplicates(ListNode *head) {
        if (head == NULL) {
            return NULL;
        }

        ListNode *node = head;
        while (node->next != NULL) {
            if (node->val == node->next->val) {
                node->next = node->next->next;
            } else {
                node = node->next;
            }
        }
        return head;
    }
};

读到这个代码的时候再往回看题目的时候才发现题目的是排序链表，也就是相同的数字是在一起的，真的是坑。。。

大致思路一样，如果数字相同，就跳到下一个继续判断是否相同，否则判断下一个数字。
注意边界情况的处理：如果head本身为NULL，直接返回NULL；

/**
 * Definition of singly-linked-list:
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param head: head is the head of the linked list
     * @return: head of linked list
     */
    ListNode * deleteDuplicates(ListNode * head) {
        // write your code here
        if(head == NULL)
        {
            return NULL;
        }
        ListNode *p = head;
        while(p->next != NULL)
        {
            if(p->val == p->next->val)
            {
                p->next = p->next->next;
            }
            else
            {
                p = p->next;
            }
           
        }
        return head;
       
    }
};

但是某些重复的节点空间并没有释放

LintCode 112.删除排序链表中的重复元素

相关推荐