问题描述:
在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。
例如:链表
1->2->3->3->4->4->5
处理后为1->2->5
解题思路( 非递归解法):
设置两个指针,一个
curr
指针指向当前节点,一个prev
指向当前节点的前序节点,如果当前节点与它下一个节点存在重复,则当前节点一直往下移动,直到碰上第一个与它不重复的节点跳出循环,然后执行移除重复节点的动作。如果当前节点和它的下一个节点不存在重复,则前序节点和当前节点同时往下移动继续前面的判断。移除重复节点的动作:
跳出循环后,将当前节点指向第一个与它不重复的节点,前序节点重新指向新的当前节点即完成移除(断开与重复节点间的联系)操作。
注意事项:
这题要理清题干,首先它是一个排序链表,所有重复值的节点必然连续排列在一起,这可以大大简化解题思路。
其次就是头结点的特殊处理,因为要设置一前一后两个指针滑动,头结点不存在前序节点,可以创建一个虚拟头结点
dummyHead
的next
指针指向实际头结点解决。
1. 非递归解法
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
// 如果头结点为空或者只存在一个节点的链表,直接返回头结点
if (pHead == null || pHead.next == null) {
return pHead;
}
// 虚拟一个头结点指向真正的头结点,这样可以做到对于头结点逻辑统一处理
ListNode dummyHead = new ListNode(Integer.MIN_VALUE);
dummyHead.next = pHead;
// 未重复节点的前序节点
ListNode prev = dummyHead;
// 当前指向的节点
ListNode curr = pHead;
while (curr != null) {
// 如果当前节点和它的下一个节点重复
if (curr.next != null && curr.val == curr.next.val) {
// 则当前节点一直往下移动,直到和下一个节点不重复为止
while (curr.next != null && curr.val == curr.next.val) {
curr = curr.next;
}
// 跳出循环后当前节点的下一个节点为第一个不重复值的节点,当前节点往下移动指向它
curr = curr.next;
// 前一个节点指向当前节点,做到和重复的节点之间断开连接
prev.next = curr;
// 如果prev节点和curr节点间没有重复的节点,则prev节点和curr节点一起往下移动
} else {
prev = curr;
curr = curr.next;
}
}
return dummyHead.next;
}
}