双层循环遍历链表删除重复元素

84 阅读 0 评论 56 点赞

我是靠谱客的博主如意溪流，最近开发中收集的这篇文章主要介绍双层循环遍历链表删除重复元素，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1. 删除链表中的重复元素，要求是不能够使用缓冲区

由于题目要求了不能够使用额外的空间来进行辅助我们找出重复的元素，即不能够使用额外的数据结构来保存元素，所以我们不能够使用哈希表（HashSet）来辅助我们找出重复的元素了，但是我们可以普遍的做法：使用双重循环来找出重复的元素

在链表中一般是使用while循环而不使用for循环来遍历元素

其中要使用到四个指针，第一个指针first指向的是第一层for循环的当前元素，第二个指针second指向的是第二层for循环的当前元素，第三个指针p指向的是第二层for循环的当前元素的前一个元素，因为我们要删除重复的元素，关键是改变前一个前驱指针的指向即可，把前一个指针的next指向下一个元素相当于就把重复的元素删除了，第四个指针pre是第一个指针的副本，用来在第二层for循环中将第一层循环的当前元素与第二层for循环的当前元素的元素值进行比较的，判断是否相同

第一层for循环结束之后那么我们应该将第一个指针往下移动，改变指针p，second，pre的指向

我觉得最重要的是弄清楚指针的指向，假如指针不够那么应该加多一个指针直到在循环中方便我们对元素进行操作

还有就是思路清楚之后需要在写代码的时候把自己想的与对应的代码联系起来，每一句写出来的代码我们都应该做到心里有数，这句代码表示的是什么意思

2. 画出其中的指针指向图

3. 因为使用了两层for循环，那么时间复杂度为O(n ^ 2), 具体的代码如下:

public class Main{
	//内部的私有类
	private static class ListNode{
		ListNode next;
		Object value;
		public ListNode(Object value) {
			super();
			this.value = value;
		}
	}
	
	public static void main(String[] args) {
		int arr[] = {1, 2, 3, 5, 4, 2, 3, 1, 7, 9, 10};
		//利用数组生成链表
		ListNode head = new ListNode(null);
		ListNode p = head;
		for(int i = 0; i < arr.length; i++){
			p.next = new ListNode(arr[i]);
			p = p.next;
		}
		removeRepetition(head);
		ListNode p1 = head.next;
		while(p1 != null){
			System.out.print(p1.value + " ");
			p1 = p1.next;
		}
	}

	private static void removeRepetition(ListNode head){
		//for循环的第一个指针
		ListNode first = head.next;
		//for循环的第二个指针
		ListNode second = null;
		ListNode p = null;
		ListNode pre = null;
		while(first != null){
			pre = first;
			second = first.next;
			p = first;
			while(second != null){
				if(pre.value == second.value){
					p.next = second.next;
				}else{
					//注意这句代码不能够写到else外面
					p = second;
				}
				second = second.next;
			}
			first = first.next;
		}
	}
}