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

C

菜团子鼠鼠

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)

C

牛客780307272号

我的思路就是两个指针遍历，一个指针作为头结点，用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)

C

无敌俊俊

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)

Python 3

Kiter

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)

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) {
        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)

Java

又笨又懒不想上课

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)

C/C++

J.Fan

//思路很简单，就是记录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)

第四单元123

思路：使用一个虚节点作为头结点来保存结果。最后返回虚节点的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)

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)

LinuX18

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)

C/C++

JordanBelfort

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)

Java

詆調壹點

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)

JavaScript Node

♈FourBrother✅已认证♉

// 思路：当前节点值跟上个节点和下个节点都不重复的时候，就是符合要求的

function deleteDuplicates( head ) {
    // write code here
    let newHead = null
    let newPre = null
    let cur = head
    let preVal = null
    while (cur) {
        const next = cur.next
        if (cur.val !== preVal && (!next || next.val !== cur.val)) {
            const node = {
                val: cur.val,
                next: null
            }
            if (newPre === null) {
                newHead = node
                newPre = node
            } else {
                newPre.next = node
                newPre = node
            }
        }
        preVal = cur.val
        cur = next
    }
    return newHead
}

发表于 2021-11-18 16:38:10 回复(0)

易水人去

// 删节点
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        if(head == NULL || head->next == NULL) return head;
        ListNode *pre = new ListNode(666);
        pre->next = head;
        ListNode *p = pre, *q;
        while(p->next && p->next->next) {
            if(p->next->val == p->next->next->val) {
                q = p->next->next->next;
                while(q && q->val == p->next->val) q = q->next;
                p->next = q;
            } else {
                p = p->next;
            }
        }
        return pre->next;
    }
};

发表于 2017-10-07 16:46:18 回复(0)

ahac

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        ListNode *beforehead = new ListNode(0);
        ListNode *cur = beforehead;
        ListNode *p = head;
        ListNode *q = head;
        beforehead->next = head;
        while (p){
            while (q!=NULL && q->val == p->val){
                q = q->next;
            }
            //检查以p为起点的元素到已q结束的位置的元素中是否有重复元素
            if (p->next == q){
                cur = p;
                p = q;
            }
            else{
                p = q;
                cur->next = q;
            }
        }
        return beforehead->next;
    }
};

发表于 2016-05-19 09:52:48 回复(0)

老石基

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null||head.next==null)
    		return head;
    	ListNode newHead = new ListNode(head.val-1);
    	newHead.next = head;
    	ListNode cur = head;
    	ListNode last = newHead;
    	while(cur!=null&&cur.next!=null){
    		
    		if(cur.val!=cur.next.val){
    			last = cur;
    		}else{
    			while(cur.next!=null&&cur.val==cur.next.val)
    				cur = cur.next;
    			last.next = cur.next;
    		}
    		cur = cur.next;
    	}
        return newHead.next;
    }
}

发表于 2016-06-03 19:25:39 回复(5)

小Andy

//没有新建节点，只是调整节点
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) 
    {
        if (!head || !head->next)
            return head;
        if (head->val != head->next->val)
        {
            head->next = deleteDuplicates(head->next);
            return head;
        }
        else
        {
            int tmp = head->val;
            while (head->val==tmp)
            {
                head = head->next;
                if (!head)
                    return NULL;
            }
            return deleteDuplicates(head);
        }
    }
};

发表于 2017-10-28 18:01:14 回复(7)

LaLaLa2333

纪念我链表问题第一次独立AC！！！

class Solution {
public:
 ListNode *deleteDuplicates(ListNode *head) {
  int preVal = INT_MIN;
  ListNode *dummyHead = new ListNode(0);
  //dummyHead->next = head;
  ListNode *cur = dummyHead;
  ListNode *pre = dummyHead;
  while (head!=NULL)
  {
   if (head->val != preVal)
   {
    pre = cur;
    cur->next = head;
    cur = cur->next;
    preVal = head->val;
   }
   else
   {
    //如果重复，回溯到上一个节点
    cur = pre;
    cur->next = NULL;
   }
   head = head->next;
  }
  cur->next = NULL;
  return dummyHead->next;
 }
};

发表于 2019-06-16 15:51:20 回复(0)

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

输入

输出

输入

输出

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题