链表总结

链表总结
链表也是计算机中一个重要的数据结构，有单向链表，双向链表等。和数组一样都是一种线性存储结构，但是它不能像数组那样通过下标查找数据，我们必须要知道链表的头结点，然后依次遍历来查找结果，在这一点上链表劣于数组；但是如果我们想删除一个数据，链表就比数组方便了很多，可以在O(1)的时间复杂度下完成，而数组删除元素需要移动其它元素，对于一个长度为n的数组删除一个节点i，时间复杂度为O(n)。

做链表题目时，如果没有一个清晰的思路很容易就乱了，链表的题目全都是围绕它的概念展开的，我们先通过实现一个单向链表来理解链表的特点。

public class LinkedList {
	LinkedList next = null;
	int val;
	
	public LinkedList(int val) {
		this.val = val;
	}
	//在链表的尾部添加新的节点
	private void appendToTail(int val) {
		LinkedList newNode = new LinkedList(val);
		LinkedList n = this;
		while (n.next != null) {
			n = n.next;
		}
		n.next = newNode;
	}
}

下面我们通过几个例子来熟悉链表的操作。
1，在链表中删除一个节点

public LinkedList deleteNode(LinkedList head, int value) {
		LinkedList helper = head;
                        //检查头结点是否需要删除
		while (head.val == value) {
			head = head.next;
			helper = head;
		}
		
		while (head.next != null) {
			if(head.next.val == value) {
				head.next = head.next.next;
			} else {
				head = head.next;
			}
		}
		return helper;
}

解决这个问题的时候，因为需要返回头节点，因此我们必须有一个辅助节点来保存头节点，如果不需要返回，那我们就不用特意保存头结点。

2，在一个未排序的单向链表中去除重复元素
提到去重我们很容易想到了哈希表，对于这道题我们也可以用哈希开解决。

public void deleteDup(LinkedList head) {
		HashSet<Integer> set = new HashSet<Integer>();
		LinkedList pre = null;
		while(head != null) {
			if (set.contains(head.val)){
				pre.next = head.next;
			} else {
				set.add(head.val);
				pre = head;
			}
			head = head.next;
		}
}

时间复杂度是O(n), 空间复杂度时O(n); 如果我们不用哈希去做也可以，这时我们就需要两个辅助节点，current 和find，current 用来遍历链表，find用来找到相同的节点, 空间复杂度为O(1),但是时间复杂度为O(n^2), 实现如下：

public void deleDup(LinkedList head) {
		if(head == null) return;
		LinkedList current = head;
		while(current != null) {
			LinkedList find = current;
			while(find.next != null) {
				if(find.next.val == current.val){
					find.next = find.next.next;
				} else {
					find = find.next;
				}
			}
			current = current.next;
		}
}

3，给定一个单向链表，删除给定的一个节点（不知道头结点）
上面两道题都给出了头节点，我们也知道，在链表中查找一个元素，只能从头节点开始遍历，但是这道题只给定了要删除的节点，怎样完成呢？我们一定不要忘记了链表的特点，既然知道一个节点，那么我们只能从这个节点开始。因为是单向链表，因此我们不可以访问到这个节点前面的节点，只能通过“next”访问到它后面的节点。不妨换一种思考方式，不删除它，把后面节点的值赋值给要删除的节点，然后删除后面的节点，这样就解决了。代码如下：

public void deleteNode(LinkedList node) {
		if(node.next == null) return;
		node.val = node.next.val;
		node.next = node.next.next;
}

代码很简单，值得注意的是，当node为最后一个节点的时候，这道题就无解了，需要特别指出。