带你快速刷完67道剑指offer

如果你想在校招中顺利拿到更好的offer,阿秀建议你多看看前人的经验 ,比如准备简历实习上岸经历校招总结阿里、字节、腾讯、美团等一二线大厂真实面经也欢迎来一起参加秋招打卡活动 等;如果你是计算机小白,学习/转行/校招路上感到迷茫或者需要帮助,可以点此联系阿秀;免费分享阿秀个人学习计算机以来的收集到的好资源,点此白嫖;如果你需要《阿秀的学习笔记》网站中求职相关知识点的PDF版本的话,可以点此下载

# No56、删除链表中的重复结点

牛客网原题链接 (opens new window)

# 题目描述

在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5

# 示例1

输入

{1,2,3,3,4,4,5}
1

返回值

{1,2,5}
1

# 1、真的是超级笨,我服了,调试了很多遍才通过的

大概思想:采用vector保存链表中的不重复元素,然后将链表从表头开始挨个对比,一样就将当前结点保存下来,然后index++,不一样就继续向下遍历,注意边界条件。

ListNode* deleteDuplication(ListNode* pHead)
{
    if (pHead == nullptr || pHead->next == nullptr) return pHead;
    ListNode* node = (ListNode*)malloc(sizeof(struct ListNode));
    node = pHead;
    vector<int> result;
    result.push_back(node->val);
    node = node->next;
    while (node != nullptr) {
        if (result.size()!=0 && result.back() == node->val) {
            while (node!=nullptr && result.back() == node->val) {
                node = node->next;
            }
            result.pop_back();
        }
        else if (result.size() == 0 || (result.size()!=0 && result.back()!=node->val))
        {
            result.push_back(node->val);
            node = node->next;
        }	
        else
            node = node->next;
    }

    if (result.size() == 0) {
        return nullptr;
    }
    node = pHead;
    int index = 0;
    int len = result.size();
    ListNode* resultNode = (ListNode*)malloc(sizeof(struct ListNode));
    while (node != nullptr) {
        if (index<len && node->val == result[index]) {
            index++;
            resultNode = node;
            break;

        } node = node->next;
    }
    pHead = resultNode;
    while (node != nullptr) {
        if (index < len && node->val == result[index]) {
            index++;
            pHead->next = node;
            pHead = pHead->next;

        } node = node->next;
    }
    pHead->next = nullptr;//最后要设置尾点结束
    return resultNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

# 2、别人的思路和方法,三指针法,取到原来指针的前一个指针

  1. 首先添加一个头节点,以方便碰到第一个,第二个节点就相同的情况

​ 2.设置 pre ,cur指针, pre指针指向当前确定不重复的那个节点,而last指针相当于工作指针,一直往后面搜索。

if (pHead == nullptr || pHead->next == nullptr) { return pHead; }
	ListNode *Head = (ListNode*)malloc(sizeof(struct ListNode));
	ListNode* pre = (ListNode*)malloc(sizeof(struct ListNode));
	ListNode* cur = (ListNode*)malloc(sizeof(struct ListNode));
	Head->next = pHead;
	pre = Head; //pre相当于原来节点的前一个节点
	cur = Head->next; //cur相当于 原来的节点
	while (cur != nullptr) {
		if (cur->next != nullptr && cur->val == cur->next->val) {
			// 找到最后的一个相同节点
			while (cur->next != nullptr && cur->val == cur->next->val) {
				cur = cur->next;
			}
			pre->next = cur->next; //这里等于cur->next真的很棒
			cur = cur->next;
		}
		else {
			pre = pre->next;
			cur = cur->next;
		}
	}
	return Head->next;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 二刷:

# 1、三指针法,可以将元素开辟到栈上

ListNode* deleteDuplication(ListNode* pHead)
{

    if(pHead == nullptr || pHead->next == nullptr) return pHead;
    ListNode dummpyHead(0);
    dummpyHead.next = pHead;
    ListNode *pre = &dummpyHead;
    ListNode *cur = dummpyHead.next;//cur是真正工作的节点
    while(cur != nullptr){
        if(cur->next != nullptr && cur->val == cur->next->val){
            while(cur->next != nullptr && cur->val == cur->next->val)
            {
                cur = cur->next;
            }
            pre->next = cur->next;//这里还不要马上把 pre 赋值过来
            cur = cur->next;
        }else{
            pre = pre->next;
            cur = cur->next;
        }
    }
    return dummpyHead.next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 变种:删除链表中的重复结点,保留一个重复点

在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->3->4->5

ListNode* deleteDuplication(ListNode* pHead)
{
    if (pHead == nullptr) return nullptr;
    ListNode* node = (ListNode*)malloc(sizeof(struct ListNode));
    node = pHead;
    while (node != nullptr) {

        if (node->next!=nullptr && node->val == node->next->val) {//这里千万要判断node->next也不为空才可以
            while (node->next != nullptr && node->val == node->next->val) {
                node->next = node->next->next;
            }
        }
        node = node->next;
    }
    return pHead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 另一种写法

ListNode* deleteDuplication(ListNode* pHead)
{
	if (pHead == nullptr || pHead->next == nullptr) return pHead;
	ListNode dummpyHead(0);
	dummpyHead.next = pHead;
	ListNode* pre = &dummpyHead;
	ListNode* cur = dummpyHead.next;
	while (cur != nullptr) {
		if (cur->next != nullptr && cur->val == cur->next->val) {
			while (cur->next != nullptr && cur->val == cur->next->val)
			{
				cur = cur->next;
			}
			pre->next = cur;
			pre = pre->next;
			cur = cur->next;
		}
		else {
			pre = pre->next;
			cur = cur->next;
		}

	}
	return dummpyHead.next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25