删除链表中重复的节点
《剑指offer》面试题18：题目二：删除链表中重复的节点。
题目：在一个排序的链表中，如何删除重复的节点？例如，链表{1,2,3,3,4,4,5}，重复的节点删除后链表为{1,2,5}
思路：从头节点开始遍历链表，如果当前节点的值与下一个节点的值相同，那么它们就是重复的节点，都需要被删除。必须保证删除之后的链表仍然是相连的：要把当前节点的前一个节点与后面值比当前节点的值大的节点相连，中间重复的节点全部删除。如果从头节点开始就出现重复，则需要改变头节点的位置。
具体实现：定义三个节点变量：root，curNode，preNode分别代表链表的头节点，当前循环中遍历的节点，前一个节点。如果传入的头节点head为空，则直接返回头节点（即返回空）；如果头节点不为空且头节点的下一个节点为空，即链表只有一个节点，返回头节点；如果头节点和头节点的下一个节点都不为空，则依次遍历链表中的节点，如果当前节点的值与下一个节点的值相同，则继续向后遍历直到当前节点的值与下一个节点next的值不同，然后判断当前节点是不是头节点，如果是头节点，则将root指向下一个节点next作为新的头节点。最后将preNode的指针域指向当前节点的下一个节点，然后curNode跳下一位。如果当前节点的值与下一个节点的值不同，则让preNode指向当前节点，当前节点跳下一位。最后函数返回链表的头节点root。
【删除链表中重复的节点】代码如下：
// 节点类
public class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}// 删除链表中重复节点的方法
public ListNode deleteDuplication(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 定义三个指针分别代表头指针，当前指针，当前指针的前一个指针
ListNode root = head;
ListNode preNode = head;
ListNode curNode = head;
// 循环遍历链表
while (curNode != null && curNode.next != null) {
// 当前节点的值等于下一个节点的值即为重复
if (curNode.val == curNode.next.val) {
// 向后查找所有重复的节点
while (curNode.next != null && curNode.next.val == curNode.val) {
curNode.next = curNode.next.next;
}
// 上面循环完成之后的当前节点curNode为重复的节点，需要删除。
// 如果头指针等于当前节点，则将头指针指向当前节点的下一个节点（第一个不重复的数）
if (root == curNode) {
root = curNode.next;
}
// 让当前节点的前一个节点的next域指向当前节点的下一个节点
preNode.next = curNode.next;
// 当前指针跳下一位
curNode = curNode.next;
} else {
// 当前节点和下一个节点不重复，则当前节点为下一次循环的前一个节点
preNode = curNode;
// 当前指针跳下一位
curNode = curNode.next;
}
}
// 返回链表头节点
return root;
}
推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- 标签、语法规范、内联框架、超链接、CSS的编写位置、CSS语法、开发工具、块和内联、常用选择器、后代元素选择器、伪类、伪元素。
- 「#1-颜龙武」区块链的价值是什么（）
- leetcode|leetcode 92. 反转链表 II
- BNC公链|BNC公链 | Eth2.0测试网Topaz已质押超100万枚ETH
- 【#2-戴栋】区块链可以提升哪些商业上的效率改进
- 父母链接八～未了情结
- java|java 常用知识点链接
- cocosbcx白皮书解读（一）|cocosbcx白皮书解读（一）| 区块链如何统一开发者、发行商、用户之间的利益
- 第六章|第六章 Sleuth--链路追踪