首页 > 试题广场 >

删除有序链表中重复的元素-II

[编程题]删除有序链表中重复的元素-II
  • 热度指数:171315 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给出一个升序排序的链表,删除链表中的所有重复出现的元素,只保留原链表中只出现一次的元素。
例如:
给出的链表为, 返回.
给出的链表为, 返回.

数据范围:链表长度 ,链表中的值满足
要求:空间复杂度 ,时间复杂度
进阶:空间复杂度 ,时间复杂度
示例1

输入

{1,2,2}

输出

{1}
示例2

输入

{}

输出

{}

说明:本题目包含复杂数据结构ListNode,点此查看相关信息
struct ListNode* deleteDuplicates(struct ListNode* head ) {
    // write code here
    if(head == NULL || head->next == NULL)//链表为空或者只有一个,直接返回
    {
        return head;
    }
    struct ListNode*h = NULL;//创建一个新单链表,这是头节点
    struct ListNode*t = NULL;//尾结点
    struct ListNode*pnew = NULL;//新结点
    struct ListNode*p = head;
    while(p)
     {
        if(p->next!=NULL && p->val == p->next->val)
        {
            while(p->next != NULL && p->val == p->next->val)//用while找到所有相同的数
            {
                p = p->next;
            }
           p = p->next;//往下走一步,所有相同的都没有获取
        } 
        else if(p->val != p->next->val)//获取不同的数
        {
             struct ListNode* pnew = malloc (sizeof(struct ListNode));
             pnew->val = p->val;
             pnew->next = NULL;
            if(h == NULL)//从无到有
            {
               h = pnew;
               t = pnew;
            }
            else//尾插
            {
                t->next = pnew;
                t = pnew;
            }
             p = p->next;
         }
    }
    return h;
}

发表于 2022-07-23 13:58:37 回复(0)
我的思路就是两个指针遍历,一个指针作为头结点,用t记录前一个结点的值,相等就跳过,不等就接上头结点,链表的最后一个元素由于fast到空指针会跳过,循环出来再判别要不要接上。
struct ListNode* deleteDuplicates(struct ListNode* head ) {
    // write code here
    if(head==NULL)
        return head;
    struct ListNode*slow=head,*fast=head->next;
    struct ListNode*p1=(struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode*p2=p1;
    int t=-1001;
    while(fast){
        if(slow->val==fast->val||slow->val==t){
            t=slow->val;
            slow=slow->next;
            fast=fast->next;
        }
        else{
            p1->next=slow;
            p1=p1->next;
            slow=slow->next;
            fast=fast->next;
            t=p1->val;
        }
    }
    if(slow->val!=t){
        p1->next=slow;
        p1=p1->next;
    }
    p1->next=NULL;
    return p2->next;   
}

发表于 2022-05-24 20:16:40 回复(0)
func deleteDuplicates( head *ListNode ) *ListNode {
    // write code here
    Head:=new(ListNode)
    Head.Next=head
    pre:=Head
    tmp:=head
    isUnique:=true
    for tmp!=nil && tmp.Next!=nil{
        if tmp.Val==tmp.Next.Val{
            isUnique=false
            tmp.Next=tmp.Next.Next
        }else{
            if !isUnique{
                isUnique=true
                pre.Next=tmp.Next
                tmp=pre.Next
            }else{
                pre=pre.Next
                tmp=tmp.Next
            }
        }
    }
    if !isUnique{
        pre.Next=tmp.Next
    }
    return Head.Next
}

发表于 2022-04-21 15:37:27 回复(0)
通过字典完成对数据频次的统计,然后生成链表
#############  Methond 1 ############## 
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
#
# from collections import defaultdict
class Solution:
    def deleteDuplicates(self , head: ListNode) -> ListNode:
        # 判断空链表和单值链表 
        if (not head)&nbs***bsp;(not head.next):
            return head 
        # 通过列表生成链表 
        l = []
        cur = head 
        while cur:
            l.append(cur.val)
            cur = cur.next 
        ## 初试化字典 
        v = 0
        dic = {k:v for k in l}
        ## 统计数值的频次 
        for i in l:
            dic[i] += 1
        
        ## 生成新的列表。这里已经去除了多次出现的数据 
        l = []
        for k, v in dic.items():
            if v <= 1:
                l.append(k)
                
        # 通过列表生成链表 
        res = head = ListNode(0)  ## 设置头结点,省去了条件判断 
        for i in range(0, len(l)):
            res.next = ListNode(l[i])
            res = res.next 
        return head.next

优化:


class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
#
# from collections import defaultdict
class Solution:
    def deleteDuplicates(self , head: ListNode) -> ListNode:
        # write code here
        # 判断空链表和单值链表 
        if (not head)&nbs***bsp;(not head.next):
            return head 
        # 通过列表生成链表 
        l = []
        cur = head 
        while cur:
            l.append(cur.val)
            cur = cur.next 
            
        ## 初试化 带有频次的字典 
        import collections 
        dic = collections.Counter(l)
        
        ## 列表生成式 
        l = [k for k,v in dic.items() if v <= 1]
                
        # 通过列表生成链表 
        res = head = ListNode(0)  ## 设置头结点,省去了条件判断 
        for i in range(0, len(l)):
            res.next = ListNode(l[i])
            res = res.next 
        return head.next



发表于 2022-04-10 10:19:12 回复(1)
C 语言写的:

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static,防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @return ListNode类
 */

typedef struct ListNode Node;
struct ListNode* deleteDuplicates(struct ListNode* head ) {
    // write code here
    if(head == NULL || head->next == NULL)
    {
        return head;
    }
    
    Node *pre = NULL;
    Node *mid = head;
    Node *cur = mid->next;
    //开头重复
    if(mid->val == cur->val)
    {
        while(cur && mid->val == cur->val)
        {
            //每次循环释放mid结点
           Node *p3 = mid;
            mid = cur;
            cur = cur->next;
            free(p3);
            if( !cur)
            {
                return NULL;
            }
        }
        //释放cur结点前一个的mid结点
        Node *p4 = mid;
        pre = cur;
        mid = cur->next;
        if(cur->next ==  NULL)
        {
            cur = NULL;
        }
        else
        {
             cur = cur->next->next;
        }
       
        printf("%d ",pre->val);
        head = pre;
        free(p4);
    }
    
    
    
    //中间重复
    while(cur)
    {
        //如果删除后的首结点还重复,继续删除
        while(1)
        {
            //如果头结点和第二个结点重复,则删除,一直删到不重复为止
            if(pre->val == mid->val && pre )
            {
            while(cur && pre->val == mid->val)
            {
                
                Node *p5 = pre;
                pre = mid;
                mid = cur;
                cur = cur->next;
                free(p5);
               
            }
                //各结点后移
               Node *p6 = pre;
               pre = mid;
               mid = cur;
                //如果cur不为空。则cur后移
               if(cur)
               {
                   cur = cur->next;
               }
               free(p6);
               head = pre;
            }
            else
            {
                break;
            }
        }
        //到这一步说明前面的已经没有重复了,只存在中间重复或者末尾重复
        if(mid->val == cur->val && mid != cur)
        {
            Node *p1 = cur;
            cur = cur->next;
            free(p1);
            //结尾重复
            //如果cur为空,直接让pre指向空,并释放mid结点和cur结点
            if(!cur)
            {
                pre->next = NULL;
                free(mid);
                free(cur);
                return head;
            }
            //如果cur的值不等于mid的值并且cur不为空,则cur后移,并同时删除mid结点
            if(cur->val != mid->val && cur)
            {
                Node *p2 = mid;
                mid = cur;
                cur = cur->next;
                free(p2);
            }
           //此时mid结点的值已经不等于cur结点的值,直接让pre结点指向mid结点,让链表连接起来
            pre->next = mid;
            
        }
        else
        {
            //都不相等,直接后移
            pre = mid;
            mid = cur;
            cur = cur->next;
        }
    }
    
    return head;
}


发表于 2022-03-13 19:42:21 回复(0)
class Solution:
    def deleteDuplicates(self , head: ListNode) -> ListNode:
        if head is None:
            return head
        dummyhead = ListNode(0)
        dummyhead.next = head
        cur = dummyhead
        pre = cur # 记录重复元素的前一位指针
        flag = 0  # 重复标志位
        while cur.next :
            cur = cur.next # 向前走一步
            while cur.next and cur.next.val == cur.val:  # 判断重复
                flag = 1
                cur = cur.next
            if flag == 1:
                pre.next = cur.next  # 去重
                flag = 0
            else:
                pre = cur

        return dummyhead.next​
发表于 2022-03-08 12:27:08 回复(0)
import java.util.*;
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */
public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        if (head == null) return null;
        ListNode dummy = new ListNode(-1), curr = head, start = dummy;
        dummy.next = head;
        while (curr.next != null) {
            if (curr.val != curr.next.val) {
                curr = curr.next;
                start = start.next;
                continue;
            }
            while (curr.next != null && curr.val == curr.next.val) {
                curr = curr.next;
            }
            if (curr.next == null) {
                start.next = null;
                break;
            }
            curr = curr.next;
            start.next = curr;
        }
        return dummy.next;
    }
}
发表于 2021-12-16 20:51:40 回复(0)
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null)  return head;
        ListNode realHead = new ListNode(-1);
        realHead.next = head;
        ListNode fast = head;
        ListNode slow = realHead;
        while(fast!=null && fast.next!=null)
        {
            if(fast.next!=null && fast.val == fast.next.val)
            {
                while(fast.next!=null && fast.val == fast.next.val)
                {
                    fast = fast.next;
                }
                slow.next = fast.next;
                fast = fast.next;
            }
            else
            {
                fast = fast.next;
                slow = slow.next;
            }
        }
        return realHead.next;

    }
}

发表于 2021-06-15 09:42:28 回复(0)
其实这一题可以在上一题的基础上加一点东西,上一题是删除相同,只保留一个,那么我们可以分为两步,第一步:删除相同,保留一个;第二步:删除那一个。
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        if(head == NULL || head->next == NULL)
            return head;
        
        ListNode preHead(0);
        preHead.next = head;
        
        ListNode *preNow = &preHead;
        ListNode *now = head;
        ListNode *pre = head,*p = head->next;
        
        int flag = 0;
        
        while(now != NULL)
        {
            while(p != NULL)
            {
                if(p->val == now->val)
                {
                    pre->next = p->next;
                    delete p;
                    p = pre->next;
                    flag++;
                }
                else
                {
                    pre = p;
                    p = pre->next;
                }
            }
            
            
            if(flag)
            {
                preNow->next = now->next;
                delete now;
                now = preNow->next;
                
                pre = now;
                if(pre != NULL)
                    p = pre->next;
                flag = 0;
            }
            else
            {
                preNow = now;
                now = now->next;
                
                pre = now;
                if(pre != NULL)
                    p = pre->next;
            }
        }
        
        head = &preHead;
        head = head->next;
        return head;
    }
};

发表于 2019-07-31 14:12:22 回复(0)
//两种写法,递归和非递归
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        //非递归
        /*
        if(!head || !head->next){
            return head;
        }
        ListNode *root = new ListNode(head->val-1);
        root->next = head;
        ListNode *pre = root;
        ListNode *cur = head;
        
        while(cur && cur->next){
            if(cur->val != cur->next->val){
                pre = cur;
                
            }else{
                while(cur->next!=NULL && cur->val == cur->next->val){
                    cur = cur->next;
                }
                pre->next = cur->next;
            }
            cur = cur->next;
        }
        return root->next;
        */

        //递归
        if(!head || !head->next){
            return head;
        }
        ListNode *root = new ListNode(head->val - 1);
        root->next = head;
        ListNode *cur = head;
        if(cur->next && cur->val != cur->next->val){
            cur->next = deleteDuplicates(cur->next);
            return cur;
        }else{
            int tmp = cur->val;
            while(cur->next && cur->next->val == tmp){
                cur = cur->next;
                if(!cur){
                    return NULL;
                }
            }
            return deleteDuplicates(cur->next);
        }
    }
};

发表于 2019-06-24 09:55:20 回复(0)
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        if(!head || !head -> next) return head;
        ListNode * dummy = new ListNode(0);
        dummy -> next = head;
        ListNode *pre = dummy, *cur = head, *nextNode = head -> next;
        while(cur && nextNode){
            if(cur -> val == nextNode -> val){
                while(nextNode && cur -> val == nextNode -> val){
                    cur -> next = nextNode -> next;
                    delete nextNode;
                    nextNode = cur -> next;
                }
                delete cur;
                pre -> next = nextNode;
                cur = nextNode;
                if(nextNode) nextNode = nextNode -> next;
            }
            else{
                pre = cur;
                cur = cur -> next;
                nextNode = nextNode -> next;
            }
        }
        head = dummy -> next;
        delete dummy;
        return head;
    }
};

发表于 2019-04-15 15:59:09 回复(0)
//思路很简单,就是记录val值相同的节点个数,有多个的话只修改前一个不重复节点的后继节点
//只有一个的话就将前一个不重复节点向后移
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        if(head == NULL)
            return NULL;
        ListNode *L = new ListNode(0);
        L->next = head;
        ListNode *p,*q,*tmp;
        p = L;
        q = head;
        int count;
        while(q!=NULL)
        {
            count = 0;
            tmp = q;
            while(q!=NULL && q->val==tmp->val)
            {
                count++;
                q = q->next;
            }
            if(count>1)
            {
               p->next = q;
            }else if(count==1){
               p->next = tmp;
               p = p->next;
            }
        }
        p->next = NULL;
        return L->next;
    }
};

发表于 2019-01-08 21:02:12 回复(0)

思路:使用一个虚节点作为头结点来保存结果。最后返回虚节点的next。使用指针p遍历链表,遇到p.next.val != p.val时认为不是重复结点,加入结果链表,或遇到尾节点时也加入。若遇到重复结点全部删除后继续处理。
最后需要注意的是将结果链表的尾节点的next设置为null,防止和其他结点相连。

    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0),pNewList = dummy;
        ListNode p = head;
        while(p != null) {
            if(p.next == null || p.val != p.next.val) {
                pNewList.next = p;
                pNewList = p;
                p = p.next;
            } else {
                int sameVal = p.val;
                for(p = p.next; p != null && p.val == sameVal; p = p.next)
                    ;
            }
        }
        pNewList.next = null;

        return dummy.next;
    }
编辑于 2018-12-07 12:24:26 回复(0)
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        if (!head) {
            return head;
        }
        ListNode dummy(INT_MIN);
        ListNode *pre = &dummy;
        pre->next = head;
        int duplicate = INT_MIN;

        for (ListNode *p = pre->next; p;) {
            if (p && duplicate < p->val && p->next && p->val == p->next->val) {
                duplicate = p->val;
                p = pre->next = p->next->next;
            } else {
                pre = p;
                p = p->next;
                continue;
            }
            while (p && p->val == duplicate) {
                p = pre->next = p->next;
            }

        }
        return dummy.next;
    }
};
发表于 2018-09-12 22:14:03 回复(0)
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        if(head == NULL || head->next == NULL)
        	return head;
        ListNode *L = new ListNode(-1);
        L->next = head;
        ListNode *p = L;
        ListNode *q = L->next;
        while(q)
        {
        	while(q->next && q->next->val == q->val)
        		q = q->next;
        	if(p->next != q)
        	{
        		ListNode *t = q->next;
        		q->next = NULL;
        		p->next = t;
        		q = t;
			}else{
				p = q;
				q = q->next;
			}
		}
		return L->next;        
    }
};

发表于 2017-08-29 01:07:42 回复(0)
NJ头像 NJ
分享一个IDE直接可用的
#include <iostream>
using namespace std;

struct ListNode
{
	ListNode *next;
	int val;
};

ListNode* CreateListNode(int value)
{
	ListNode* pNode = new ListNode();
	pNode->val = value;
	pNode->next = NULL;
	return pNode;
}

void ConnectListNodes(ListNode* pCurrent, ListNode* pNext)
{
	if (pCurrent == NULL)
	{
		printf("Error to connect two nodes.\n");
		exit(1);
	}

	pCurrent->next = pNext;
}

void PrintList(ListNode* pHead)
{
	printf("PrintList starts.\n");

	ListNode* pNode = pHead;
	while (pNode != NULL)
	{
		printf("%d\t", pNode->val);
		pNode = pNode->next;
	}

	printf("\nPrintList ends.\n");
}

ListNode *DeleteDuplicateNode(ListNode *pHead)
{
	if (pHead == NULL)
		return NULL;
	ListNode* dummy = CreateListNode(0);
	dummy->next = pHead;
	ListNode* Pre = dummy;
	ListNode* Cur = pHead;
	while (Cur != NULL)
	{
		while (Cur->next != NULL&&Cur->val == Cur->next->val)
			Cur = Cur->next;
		if (Pre->next == Cur)
		{
			Pre = Pre->next;
			Cur = Cur->next;
		}
		else
		{
			Pre->next = Cur->next;
			Cur = Cur->next;
		}

	}
	return dummy->next;
}

void main()
{
	ListNode* pNode1 = CreateListNode(1);
	ListNode* pNode2 = CreateListNode(1);
	ListNode* pNode3 = CreateListNode(2);
	ListNode* pNode4 = CreateListNode(2);
	ListNode* pNode5 = CreateListNode(4);
	//ListNode* pNode6 = CreateListNode(4);
	//ListNode* pNode7 = CreateListNode(5);
	ConnectListNodes(pNode1, pNode2);
	ConnectListNodes(pNode2, pNode3);
	ConnectListNodes(pNode3, pNode4);
	ConnectListNodes(pNode4, pNode5);
	//ConnectListNodes(pNode5, pNode6);
	//ConnectListNodes(pNode6, pNode7);

	ListNode *zkd = DeleteDuplicateNode(pNode1);
	PrintList(zkd);
}

发表于 2017-08-02 20:59:10 回复(0)
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head)
    {
       ListNode *fake= new ListNode(0);
       fake->next = head;
       ListNode *p = fake;
       while(head)
        {
           if(head->next && head->next->val == head->val)
           {
               ListNode *temp=head->next;
               while(temp->next && temp->next->val == head->val)           
                   temp=temp->next;
               head = temp;
               p->next = temp->next;
           }
           else
           {
              p->next = head;
              p = p->next;
           }
           head = head->next;
       }
        return fake->next;
    }
};

发表于 2017-07-18 16:18:53 回复(0)
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *pHead) {
        if (pHead == NULL || pHead->next == NULL) return pHead;
        ListNode* head = new ListNode(INT_MIN);
        head->next = pHead;
        ListNode* p = head;
        ListNode* q = head->next;
        while(q) {
            while(q->next && q->next->val == q->val) q = q->next;
            if(p->next != q) {
                ListNode* tmp = q->next;
                q->next = NULL; //将重复结点断开
                p->next = tmp;
                q = tmp;
            } 
            else {
                p = q;
                q = q->next;
            }
        }
        return head->next;
    }
};

发表于 2017-03-10 17:30:03 回复(0)
public class Solution {
    public static ListNode deleteDuplicates(ListNode head) {
		if(head == null || head.next == null) return head;
		ListNode newHead = new ListNode(0);
		newHead.next = head;
		ListNode pre = newHead;
		ListNode cur = head;
		while (cur != null && cur.next != null) {
			if(cur.val != cur.next.val) pre = cur;
			else {
				while (cur.next != null && cur.val == cur.next.val)
					cur = cur.next;
				pre.next = cur.next;
			}
			cur = cur.next;
		}
		return newHead.next;
	}
}

发表于 2016-11-17 22:18:01 回复(0)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null) {
            return null;
        }
        //创建一个节点,指向头结点 -1->head
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        //用来记录不相同节点的前一个节点 例如1->2->2 则pre = 1;
        ListNode pre = dummy;
        ListNode cur = head;
        while(cur!=null && cur.next!=null) {
            if(cur.next.val!=cur.val) {
                pre = cur;
                cur = cur.next;
            }else {
                ListNode n = cur.next.next;
                int val = cur.val;
                //循环遍历 直到遇到不重复的节点
                while(n!=null) {
                    if(n.val!=val) {
                        break;
                    }
                    n = n.next;
                }
                pre.next = n;
                cur = n;
            }
            
        }
        return dummy.next;
    }
}

发表于 2016-03-14 21:35:37 回复(0)