推荐
完整《剑指Offer》算法题解析系列请点击 👉 《剑指Offer》全解析 Java 版
题目描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */
public class Solution {
public ListNode deleteDuplication(ListNode pHead)
{
}
}
**参考思路：**递归检查。
因为是有序的链表，比较简单。
- 检查当前结点与下一个结点是否相同。
- 如果下一个结点和当前结点重复，我们一直向后检查，找到第一个和当前结点不重复的结点，将当前结点的下一个结点指向它，并将这个结点作为新的当前结点，重复第一步。
- 如果下一个结点和当前结点不重复，那么直接将下一个结点作为新的当前结点，重复第一步。
参考实现：
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */
public class Solution {
public ListNode deleteDuplication(ListNode pHead)
{
//只有0个或1个结点，直接返回即可
if (pHead == null || pHead.next == null) {
return pHead;
}
//如果当前结点是重复结点
if (pHead.val == pHead.next.val) {
ListNode pNode = pHead.next;
//跳过与当前结点值相同的全部结点，找到第一个与当前结点不同的结点
while (pNode != null && pNode.val == pHead.val) {
pNode = pNode.next;
}
//递归检查下一个不同的结点并返回结果
return deleteDuplication(pNode);
} else {
//如果当前结点不是重复的结点，检查下一个结点，并返回链表头指针
pHead.next = deleteDuplication(pHead.next);
return pHead;
}
}
}
看完之后，如果还有什么不懂的，可以在评论区留言，会及时回答更新。
这里是猿兄，为你分享程序员的世界。
非常感谢各位大佬们能看到这里，如果觉得文章还不错的话， 求点赞👍 求关注💗 求分享👬求评论📝 这些对猿兄来说真的 非常有用！！！
注： 如果猿兄这篇博客有任何错误和建议，欢迎大家留言，不胜感激！
京公网安备 11010502036488号