删除排序链表中重复元素的方法

冬天里的懒猫

发布于 2020-08-03 20:59:47

1K0

发布于 2020-08-03 20:59:47

链表的操作非常常见，也是面试中经常会被问道的问题。对于链表重复元素的删除，有两个变体，现在总结如下。链表代码如下：

	public class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
		}
	}

1.删除重复元素，所有元素只保留一次。

 * @description 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
 * 示例 1:
 * 输入: 1->1->2
 * 输出: 1->2
 * 示例 2:
 * 输入: 1->1->2->3->3
 * 输出: 1->2->3
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list

这个问题的解法非常简单，只需要定义一个指针然后while循环即可。

	public ListNode deleteDuplicates(ListNode head) {
		ListNode cur = head;
		while (null!=cur&&null!=cur.next){
			if(cur.val == cur.next.val){
				if(null != cur.next.next){
					cur.next = cur.next.next;
				}else {
					cur.next = null;
				}
			}else {
				cur = cur.next;
			}
		}
		return head;
	}

定义一个指针cur，然后循环判断cur.value和cur.next.value，如果相等，那么就将后面重复元素移除。如果不等，则指针后移。

2.删除全部重复的元素，只保留没有重复的元素。

*@description
 * 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
 * 示例 1:
 * 输入: 1->2->3->3->4->4->5
 * 输出: 1->2->5
 * 示例 2:
 * 输入: 1->1->1->2->3
 * 输出: 2->3
 * 链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii

本文需要重点关注的是这个变体，因为问题1的解法很简单。没什么特别的。但是加上了将全部重复的数字都去除这个条件之后，难度瞬间增加了不少。你需要考虑两个问题：

如果链表头就是重复的数字怎么办
如何移动比较链表，删除元素？

第一，对于表头重复的问题，那么最简单的办法就是在表头添加一个元素，加入链表。之后在链表遍历完之后，返回哨兵的next。这是一个非常好的办法，简直是以后解决链表类问题的套路之一。

	ListNode cur = new ListNode(0);
		cur.next = head;
		head = cur;

仅仅三行代码就搞定了。第二，对于如何移动比较的问题，此时发现，用一个指针无论如何也无法实现题目的需求了。此时看到了参考文档中的三指针法。现在将文章中的内容发下来：除了哨兵之外，需要定义一个left和一个right两个指针。

先用right和right下一个元素比较，如果相等，则left移动。之后循环判断left和right两个指针是否指向同一个元素。如果相等，则说明没有相同的元素。哨兵cur向后移动。反之，则说明存在相同的元素，哨兵则将当前next指针指向right.next,将重复元素都删除。完整算法如下：

	public ListNode deleteDuplicates(ListNode head) {
		ListNode cur = new ListNode(0);
		cur.next = head;
		head = cur;
		ListNode left,right;
		while (null!=cur&&null!=cur.next){
			left = cur.next;
			right = cur.next;
			while (null!=right.next&&right.next.val==left.val){
				right = right.next;
			}
			if(right == left){
				cur = cur.next;
			}else {
				cur.next = right.next;
			}
		}
		return head.next;
	}

三指针法，也是一个经典的算法。在后续面链表相关问题的时候，又是一个新套路。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/07/09 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度