admin管理员组

文章数量:1596328

Qustion:

Given a sorted linked list, and remove all the nodes which have duplication. For example, 1 -> 1 -> 2 -> 2 -> 3 ->4 , after removing duplicates, the linked list becomes 3 ->4.

Analyze:

1. In order to remove the duplicated nodes in the list, we consider the duplicates as a composite node. After removing the composite node, we need to make sure that  remaining nodes are still connected. Therefore, we need to have a pointer which points to the parent node of the composite node. When the composite node is removed, the parent node will point to the next non-duplicated node.

2. If the first node belongs to a composite node, we need to return a new head.

Code:

public static Node removeDuplication(Node head) {
	if (head == null || head.next == null ) return head;
	//father node
	Node prev = null;
	Node newHead = null;
	//if the newhead has been determined,
	//we will not change the head any more.
	boolean headunchanged = true;
	
	while (head != null) {
		// if true, we will remove the composite node
		if (head.next != null && head.value == head.next.value) {
			while (head.next != null && head.value == head.next.value) {
				head = head.next;
			}
			head = head.next;
			if (head == null && prev != null) {
				prev.next = null;
			}
			
		} else {
			//change head if applicable
			if (headunchanged == true) {
				newHead = head;
				headunchanged = false;
			}
			//update the next value in the prev node
			if (prev != null) {
				prev.next = head;
			}
			prev = head;
			head = head.next;
		}
	}
	return newHead;		
}
http://blog.csdn/beiyeqing teng

本文标签： DuplicatesEliminatesortedListLinked

版权声明：本文标题：eliminate the duplicates in a sorted linked list (1) 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.elefans.com/xitong/1728256306a1151055.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。