首页 > 试题广场 >

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

[编程题]删除有序链表中重复的元素-I

热度指数：198710 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次
例如：
给出的链表为 $1\to1\to2$ ,返回 $1 \to 2$ .
给出的链表为 $1\to1\to 2 \to 3 \to 3$ ,返回 $1\to 2 \to 3$ .

数据范围：链表长度满足 $0 \le n \le 100$ ，链表中任意节点的值满足 $|val| \le 100$

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

{1,1,2}

输出

{1,2}

示例2

输入

{}

输出

{}

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

算法知识视频讲解

勇敢牛牛，不怕困难！

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

class Solution {
public:
  /**
   * 
   * @param head ListNode类 
   * @return ListNode类
   */
  ListNode* deleteDuplicates(ListNode* head) {
    // 维护住循环不定式(loop invariant)
    // 从头指针指向的节点到curr指向的节点之间不存在重复的元素!
    ListNode* curr = head;
    while (curr && curr->next) {
      if (curr->val == curr->next->val) {
        ListNode* node_to_delete = curr->next;
        curr->next = curr->next->next;
        delete node_to_delete;
      } else {
        curr = curr->next;
      }
    }
    return head;
  }
};

发表于 2021-07-06 14:22:14 回复(0)

keeprealandconfidence

思路是以当前结点的值为依据，向后查找，直到找到值不相等的结点。代码如下：

/**
 * 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) {
        ListNode * p=head;
        while(p!=NULL&&p->next!=NULL)
        {
            ListNode * q=p->next;
            while(q!=NULL&&q->val==p->val)
            {
                q=q->next;
            }
            p->next=q;
            p=q;
        }
        return head;
    }
};

发表于 2019-08-08 20:44:00 回复(1)

NothingCoder

public ListNode deleteDuplicates(ListNode head) {
		
		ListNode cur = head;
		while(cur != null){
			while(cur.next != null && cur.val == cur.next.val){
				cur.next = cur.next.next;
			}
			cur = cur.next;
		}
		return head;
	}

发表于 2016-07-19 17:18:21 回复(23)

此广告位出租

        ListNode p=head,q=head;
        while (p != null && q != null){
            if (q.val == p.val){
                p.next = q.next;
            } else {
                p = p.next;
            }
            q = q.next;
        }
        return head;

编辑于 2018-05-22 14:49:19 回复(0)

萨达哈鲁

public class Solution {
    public ListNode deleteDuplicates (ListNode head) {
        ListNode tou = head;
        while(head != null && head.next != null) {
            if(head.val == head.next.val) {
                head.next = head.next.next;
            } else {
                head = head.next;
            }
        }
        return tou;
    }
}

一个while搞定得了。重复的就不往后走，一直删。不重复指针在往后移动一位即可。

发表于 2020-06-29 08:21:25 回复(0)

C/C++

QT菜鸡弟弟

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        ListNode *cur = head;
        while(cur != NULL){
            while(cur->next != NULL && cur->val == cur->next->val){
                cur->next = cur->next->next;
            }
            cur = cur->next;
        }
        return head;
    }
};

发表于 2019-09-20 10:24:32 回复(0)

Java

Nakangzi

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        if(head==null||head.next==null)return head;
        ListNode cur=head;
        while(cur!=null&&cur.next!=null){
            if(cur.next.val==cur.val){
                cur.next=cur.next.next;
            }
            else cur=cur.next;
        }
        return head;
    }
}

发表于 2020-08-25 17:46:32 回复(2)

C/C++

努力的牛牛

    /*
    * 目的：删除链表中重复元素，只保留一次
    * 方法：新建一个头节点，
    *      如果当前节点与next节点的值相等，则分别移至下一个节点，
    *      否则插入到新的链表中，最后返回dummy.next
    */
    ListNode *deleteDuplicates(ListNode *head) {
        if (head == nullptr)
            return head;
        ListNode dummy(-1);
        ListNode*pre = &dummy;
        ListNode*next =nullptr;
        while(head){
            next = head->next;
            if (next==nullptr || head->val != next->val)
            {
                head->next = nullptr;
                pre->next = head;
                pre=pre->next;
            }
            head=next;
        }
        return dummy.next;
    }

发表于 2019-12-09 09:32:00 回复(0)

C/C++

JordanBelfort

//要断开无用的指针,防止内存泄露
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        if(head == NULL || head->next == NULL) return head;
        ListNode* p1 = head;
        while(p1 != NULL && p1->next != NULL) {
            ListNode* p2 = p1->next;
            if(p1->val != p2->val) {
                p1->next = p2;
                p1 = p1->next;
                continue;
            }
            while(p2->next != NULL && p1->val == p2->next->val) p2 = p2->next;
            p1->next = p2->next;
            delete p2;
            p1 = p1->next;
        }
        return head;
    }
};

编辑于 2017-03-10 14:55:15 回复(1)

一个优雅的程序猿

struct ListNode* deleteDuplicates(struct ListNode* head ) {
    struct ListNode *res, *p=head->next;
    if(head==NULL || head->next==NULL)
        return head;
    res = deleteDuplicates(head->next);
    while(p!=NULL) {
        if(p->val == head->val)
            return res;
        p = p->next;
    }
    head->next = res;
    return head;
}

发表于 2024-03-15 23:38:15 回复(0)

Java

Sillyou

import java.util.*;

public class Solution {

public ListNode deleteDuplicates (ListNode head) {

ListNode p = head;

// && 运算符：若左编false，就不会判断右边

while(p != null && p.next != null) {

if(p.val == p.next.val) {

p.next = p.next.next;

} else {

p = p.next;

}

return head;

}

发表于 2023-03-28 17:26:58 回复(0)

Python3

牛客1217718号

class Solution:

def deleteDuplicates(self , head: ListNode) -> ListNode:

cur = head

while cur and cur.next:

nex = cur.next

if nex.val <= cur.val:

cur.next = nex.next

else:

cur = nex

return head

发表于 2022-09-30 21:51:48 回复(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) {
        ListNode dummy=new ListNode(0);
        dummy.next=head;
        ListNode node=dummy;
        while(node.next!=null&&node.next.next!=null){
            if(node.next.val==node.next.next.val){
                node=node.next;
                int x=node.next.val;
                while(node.next!=null&&node.next.val==x){
                    node.next=node.next.next;
                }
            }
        else node=node.next;
    }
        return dummy.next;
}
}

如果要删除所有存在重复的元素

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 dummy=new ListNode(0);
        dummy.next=head;
        ListNode node=dummy;
        while(node.next!=null&&node.next.next!=null){
            if(node.next.val==node.next.next.val){
                //node=node.next; 把这一行注释掉即可。
                int x=node.next.val;
                while(node.next!=null&&node.next.val==x){
                    node.next=node.next.next;
                }
            }
        else node=node.next;
    }
        return dummy.next;
}
}

发表于 2021-12-23 23:41:10 回复(0)

Java

小灰灰QAQ

  public ListNode deleteDuplicates(ListNode head) {
        if (head == null)
            return null;
        ListNode p = head;
        while (p.next != null) {
            if (p.next.val == p.val)
                p.next = p.next.next;
            else {
                p = p.next;
            }
        }
        return head;
    }

发表于 2021-12-13 16:00:19 回复(0)

C++

xxining

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == nullptr) return head;
        ListNode* cur = head;
        ListNode* nex = head->next;
        while(nex){
            if(cur->val == nex->val){
                cur->next = nex->next;
            }else{
                cur = nex;
            }
            nex = nex->next;
        }
        return head;
    }
};

发表于 2021-12-10 01:51:50 回复(0)

cqu后起之秀

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* deleteDuplicates(ListNode* head) {
        // write code here
        if(head == NULL) return head;
        ListNode *cur = NULL, *list = head,*next = NULL;
        while(list){
            while(list->val == list->next->val && list->next != NULL){
                cur = list->next->next;
                list->next->next = NULL;
                list->next = cur;
            }
            list = list->next;
        }
        return head;
    }
};

发表于 2021-07-06 00:00:49 回复(0)

JavaScript

IPzzzi

function deleteDuplicates( head ) {
    // write code here
    if(head == null){
        return head;
    }
    var p = head;
    while(p.next !== null){
        if(p.next.val == p.val){
            p.next = p.next.next;
        }else{
            p = p.next;
        }
    }
    return head;
}

发表于 2021-04-12 20:31:14 回复(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) {
        // write code here
        if(head==null||head.next==null) return head;
        ListNode pre=head;
        ListNode cur=head.next;
        while(cur!=null){
            if(pre.val==cur.val){
                pre.next=cur.next;
                cur=pre.next;
            } else{
                pre=cur;
                cur=cur.next;
            }
        }
        return head;
    }
}

发表于 2021-03-20 16:16:55 回复(0)

金虹桥招财猫

 //熟悉一下ListNode的 next val node
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode node = head;
        while(node != null && node.next != null){
            if(node.val == node.next.val){
                node.next = node.next.next;
            }
            else{
                node=node.next;
            }
        }
        return head;
    }
}

发表于 2020-07-15 18:42:54 回复(0)

唐子夏

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        ListNode* pre=new ListNode(-1);
        ListNode* respre=pre;
        ListNode* p=head;
        pre->next=head;
        while(p){
            ListNode* tmp=p->next;
            if(tmp!=NULL&&p->val==tmp->val){
                while(tmp&&tmp->val==p->val) {
                    p=p->next;
                    tmp=tmp->next;
                }
                pre->next=p;
                pre=p;
                p=tmp;
            }else{
                pre=p;
                p=p->next;
            }
        }
        return respre->next;
    }
};

类似于上道题，不过和上道题不同的是上道题将所有的重复节点进行删除，而这道题不用删除所有重复节点，需要保留最后一个，所以只需要在相同的后续处理中加上对应的简单操作即可！

发表于 2017-12-16 09:57:24 回复(0)