【剑指Offer】面试题57：删除链表中重复的结点

一：题目描述

在一个排序的链表中，如何删除重复的结点？

如  1->2->3->3->4->4->5

删除重复的结点后链表变成：

1->2->5

二：解题思路

如果当前节点的值与下一个结点的值相同，那么他们就是重复的结点，都可以被删除。

为了保证删除后链表仍然是相连的没有断开，我们要把当前节点的前一个节点和侯敏值比他大的结点相连。、

需要注意：

1.输入空链表

2.删除的结点可能是头结点

3.删除后链表可能为空。

三：代码实现

ListNode* deleteRepeatNode(ListNode * head){ if (head == NULL) return NULL; ListNode* deletedHead = head; ListNode* pPreNode = NULL; ListNode* pNode = head; while (pNode != NULL){ ListNode* pNext = pNode->next; bool needDelete = false; if (pNext != NULL && pNext->val == pNode->val) needDelete = true; if (!needDelete){ pPreNode = pNode; pNode = pNode->next; } else{ int val = pNode->val; ListNode* pToBeDel = pNode; while (pToBeDel != NULL && pToBeDel->val == val){ pNext = pToBeDel->next; //删除指针空间，并将指针置为NULL，防止野指针现象 delete pToBeDel; pToBeDel = NULL; pToBeDel = pNext; } //原始头结点被删除 if (pPreNode == NULL) deletedHead = pNext; else pPreNode->next = pNext; pNode = pNext; }//else }//while return deletedHead; }