龙哥网

龙哥网

Java 数据结构之删除链表中重复的结点_java
2022-03-01

目录
  • 解析一:(不提倡)
  • 解析二:(正解)

核心考点:链表操作,临界条件检查,特殊情况处理

在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。

解析一:(不提倡)

解决该问题较简单,且在写代码时不易出错的做法如下:

  1. 遍历一遍链表,记录重复结点的结点值。
  2. 再遍历一遍链表,逐个删除重复结点。

动图演示:

该方法需要遍历两遍链表,且需要开辟额外的内存空间存储重复结点的结点值,所以一般不提倡。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        if(pHead == nullptr||pHead->next == nullptr) //链表为空或只有一个结点无需进行操作
            return pHead;
        ListNode* cur = pHead;
        unordered_set<int> filter;
		//1、遍历链表找出重复的结点,将结点值存入filter
		while (cur->next)
        {
			if (cur->val == cur->next->val)
				filter.insert(cur->val);
			cur = cur->next;
        }
		//2、逐个删除重复的结点
        //先删除头部的重复结点
        while(pHead&&filter.find(pHead->val) != filter.end())
        {
            pHead = pHead->next;
        }
        if(pHead == nullptr)
            return nullptr;
        //再删除其余的重复结点
        ListNode* prev = pHead;
        ListNode* last = prev->next;
        while(last)
        {
            if(filter.find(last->val) != filter.end())
            {
                prev->next = last->next;
                last = last->next;
            }
            else
            {
                prev = prev->next;
                last = last->next;
            }
        }
        return pHead; //返回链表头指针
    }
};

解析二:(正解)

我们当然应该尽可能在遍历一遍链表的情况下解决该问题,这时我们需要使用两个指针配合完成,该过程当中包含大量细节,大致步骤如下:

1.为了后续操作方便,先为该链表创建一个头结点。

2.使用指针prev和last遍历链表,初始时prev指向头结点,last指向头结点的下一个结点。

3.当last指向的结点值与其后一个结点的结点值相同时,last独自后移,直到last指向结点的结点值与其下一个结点的结点值不同为止,此时让prev指向的结点指向last的后一个结点,最后让last指向下一个结点(图中未后移)。

4.当last指向的结点值与其后一个结点的结点值不同时,prev和last一同向后移。

如此进行下去,直到last将链表遍历完,链表当中重复的结点也就全部被删除了,最后返回头结点指向的链表即可。

动图演示:

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};*/
class Solution {
public:
	ListNode* deleteDuplication(ListNode* pHead) {
		if (pHead == nullptr || pHead->next == nullptr) //链表为空或只有一个结点无需进行操作
			return pHead;
		ListNode* head = new ListNode(0); //创建头结点(便于操作)
		head->next = pHead; //头结点与原链表建立关系
		ListNode* prev = head;
		ListNode* last = prev->next;
		while (last)
		{
			//未发现重复的结点,prev和last一同后移
			while (last->next&&last->val != last->next->val)
			{
				prev = prev->next;
				last = last->next;
			}
			//发现重复的结点,last独自后移
			while (last->next&&last->val == last->next->val)
			{
				last = last->next;
			}
			//到达此处有三种情况:
			//1、没有需要删除的重复结点,是因为last->next == nullptr到此
			//2、有需要删除的重复结点,是因为last->next == nullptr到此(链表后半段都需要删除)
			//3、有需要删除的重复结点,是因为last->val != last->next->val到此(链表中间某段需要删除)
			if (prev->next != last) //说明有需要删除的重复结点
			{
				prev->next = last->next;
			}
			last = last->next;
		}
		return head->next; //返回链表头指针
	}
}; 
免责声明
本站部分资源来源于互联网 如有侵权 请联系站长删除
龙哥网是优质的互联网科技创业资源_行业项目分享_网络知识引流变现方法的平台为广大网友提供学习互联网相关知识_内容变现的方法。