描述
题目描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
示例
输入：{1,2,3,3,4,4,5}
返回值：{1,2,5}知识点：链表、指针、
难度：⭐⭐⭐
题解
解题思路
对于链表的题目，通常有遍历和递归两种做法。
遍历需要借助图理解遍历过程，递归则需要定义好递归函数的功能以及确定好终止条件。
因为题目要求链表是有序的，因此就可以采用循环遍历判断的方法，以及递归寻找下一个不重复节点的方法。
方法一：循环遍历
图解
图解流程：
1、如上图，当前节点cur == cur.next，循环判断，直到不等于
2、cur此时指向最后一个重复节点，prev.next = cur.next，表示忽略中间的重复节点
3、prev 和 cur 继续向右遍历判断，直到 cur == null
4、最后返回 head.next ，即head指向的头节点为删除重复节点之后的链表
算法流程：
- 定义head头节点指针，prev和cur分别是前指针是当前指针
- 循环遍历：当前指针节点与下一个节点相等，则cur继续向右判断
- 忽略掉中间有重复节点的cur节点
- 不相等，则前后指针继续遍历
Java 版本代码如下：
import java.util.*;
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
// base case
if(pHead == null || pHead.next == null) {
return pHead;
}
// 定义head头节点指针，prev和cur分别是前指针和当前指针
ListNode cur = pHead, prev;
ListNode head = new ListNode(0);
head.next = pHead;
prev = head;
// 非递归
while(cur != null) {
// 当前指针节点与下一个节点相等，则cur继续向右判断
if(cur.next != null && cur.val == cur.next.val) {
while(cur.next != null && cur.val == cur.next.val) {
cur = cur.next;
}
// 忽略掉中间有重复节点的cur节点
prev.next = cur.next;
cur = cur.next;
} else {
// 不相等，则前后指针继续遍历
prev = prev.next;
cur = cur.next;
}
}
// 返回链表
return head.next;
}
} Python 版本代码如下：
class Solution:
def deleteDuplication(self, pHead):
# 定义头节点指针，前指针和当前指针
p0 = ListNode(-1)
p = p0
p.next = pHead
cur = pHead
# 循环遍历
while cur and cur.next:
# 不相等，则前后指针继续遍历
if cur.val != cur.next.val:
p = p.next
cur = cur.next
else:
# 出现重复节点，即当前指针节点与下一个节点相等，则cur继续向右判断
val = cur.val
while cur and cur.val == val:
cur = cur.next
p.next = cur
return p0.next 复杂度分析：
时间复杂度 O(N)：需要遍历链表，N为链表长度
空间复杂度 O(1)：只用到定义的指针
总结：对于链表的遍历做法，通常需要结合图来理解
方法二：
算法流程：
- 每次进入方法都需要判断：当前结点是否是重复结点
- 如果是，继续循环遍历判断是否还是重复节点, 每次跳过值与当前结点相同的全部结点,找到第一个与当前结点不同的结点
- 从第一个与当前结点不同的结点开始递归
- 如果当前结点不是重复结点，保留当前结点，从下一个结点开始递归
Java 版本代码如下：
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
if (pHead == null || pHead.next == null) return pHead;
if (pHead.val != pHead.next.val) {
// 当前结点不是重复结点
// 保留当前结点，从下一个结点开始递归
pHead.next = deleteDuplication(pHead.next);
return pHead;
} else {
// 当前结点是重复结点
// 继续循环遍历判断是否还是重复节点
ListNode pNode = pHead;
while (pNode != null && pNode.val == pHead.val) {
// 跳过值与当前结点相同的全部结点,找到第一个与当前结点不同的结点
pNode = pNode.next;
}
// 从第一个与当前结点不同的结点开始递归
return deleteDuplication(pNode);
}
}
}
复杂度分析：
时间复杂度 O(N)：递归操作需要栈空间
空间复杂度 O(1)：只用到定义的指针
京公网安备 11010502036488号