Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Remove Duplicates from Sorted List II

Leetcode algorithms 第 82 题:Remove Duplicates from Sorted List II 。

题目

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

解答

删除链表出现次数大于1的所有节点。基本思想是逐个遍历链表的节点,当某个节点的值与其后续节点的值相同时,则删除本身及其后所有为这个值的节点。

考虑到可能出现链表所有元素的值都相同的情况,使用一个辅助的头结点dummy,把所有只出现一次的节点连接到这个头结点中,这样dummy.next即为答案。如果所有元素都一样,则dummy.next为NULL,同样是答案。

具体代码如下:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        if (head == NULL || head->next == NULL) return head;
        
        ListNode dummy(-1); //辅助头结点
        
        ListNode *p1 = &dummy, *p2 = head; //p1为答案的末尾节点,p2为遍历的当前节点
        while (p2 != NULL)
        {
            if (p2->next == NULL || p2->val != p2->next->val)
                p1->next = p2, p1 = p1->next, p2 = p2->next;
            else //p2与下一个节点的值相同
            {
                int v = p2->val;
                while(p2 && p2->val == v) //删除所有值等于v的节点
                {
                    ListNode *tem = p2->next;
                    delete(p2);
                    p2 = tem;
                }
            }
        }
        
        p1->next = NULL; //末尾节点的next设置为NULL
        return dummy.next;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论