admin管理员组文章数量:1596416
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://m.elefans.com/xitong/1728256306a1151055.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论