题目描述
在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5
题解:
int value用来存储当前节点的节点值,创建一个新的链表节点用于连接符合存储条件的节点;比较当前节点的下一个节点值和当前节点的值是否相等;用tip记录状态int tip=0,节点值相等:tip=1;节点值不等:tip=0;
- 当前节点与下一个节点的值不等时:
如果tip=0,说明上次判断时节点值也不等,所以当前节点与上一个节点的节点值也不相等,可以连接该节点;
如果tip=1,说明上次判断时节点值相等,此时我们只需要更新value,让它等于下一个节点的值即可; - 当前节点与下一个节点的值相等时:
将tip状态更改为1; - 考虑边界条件,当前节点是尾节点时:
根据tip判断出当前节点和上一个节点是否相等:不等的话让新节点的next连接该节点;相等则令新节点的next指向NULL;
My Solution(C/C++完整实现):
#include <cstdio>
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode * deleteDuplication(ListNode* pHead) {
ListNode result(0);
ListNode *new_head = &result;
int value = pHead->val;
int tip = 0;
while (pHead) {
if (pHead->next && pHead->next->val == value) {
tip = 1;
}
else if(pHead->next && pHead->next->val != value) {
if (tip == 0) {
//可以存节点!
new_head->next = pHead;
new_head = new_head->next;
}
value = pHead->next->val;
tip = 0;
}
else {
if (tip == 0) {
new_head->next = pHead;
}
else {
new_head->next = NULL;
}
}
pHead = pHead->next;
}
return result.next;
}
};
int main() {
ListNode a(1);
ListNode b(2);
ListNode c(3);
ListNode d(3);
ListNode e(4);
ListNode f(5);
ListNode g(5);
a.next = &b;
b.next = &c;
c.next = &d;
d.next = &e;
e.next = &f;
f.next = &g;
Solution s;
ListNode *result = s.deleteDuplication(&a);
while (result) {
printf("%d->", result->val);
result = result->next;
}
return 0;
}
结果:
1->2->4->