剑指offer-56、删除链表中重复的节点
<h2 id="题描述">题⽬描述</h2><p>在⼀个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5</p>
<p>示例1<br>
输⼊：{1,2,3,3,4,4,5}<br>
返回值：{1,2,5}</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="hash统计">hash统计</h3>
<p>第一次遍历统计频率，第二次遍历删除重复节点</p>
<pre><code class="language-java">import java.util.HashMap;
public class Solution {
public ListNode deleteDuplication(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 第一次遍历：统计每个节点值出现的次数
HashMap<Integer, Integer> countMap = new HashMap<>();
ListNode current = head;
while (current != null) {
countMap.put(current.val, countMap.getOrDefault(current.val, 0) + 1);
current = current.next;
}
// 第二次遍历：删除重复节点
ListNode dummy = new ListNode(-1); // 哑节点简化边界处理
dummy.next = head;
ListNode prev = dummy;
current = head;
while (current != null) {
if (countMap.get(current.val) > 1) {
// 当前节点重复，跳过
prev.next = current.next;
} else {
// 当前节点不重复，移动prev指针
prev = prev.next;
}
current = current.next;
}
return dummy.next;
}
}
</code></pre>
<ul>
<li>时间复杂度：O(n)</li>
<li>空间复杂度：O(n)</li>
</ul>
<h3 id="直接遍历推荐">直接遍历（推荐）</h3>
<p>注意，题目已经提到是排序的节点，那么就可以直接原地删除</p>
<p>对⽐前后两个元素，如果相同的情况下，接着遍历后⾯的元素，直到元素不相等的时候，将前⾯的指针指向最后⼀个相同的元素的后⾯，相当于跳过了相同的元素。</p>
<pre><code class="language-java">public class Solution {
public ListNode deleteDuplication(ListNode pHead)
{
//遍历链表，直接删除
if(pHead == null || pHead.next == null) return pHead;
ListNode head = new ListNode(0);
head.next = pHead;
ListNode cur = head.next;
ListNode pre = head;
while(cur != null){
//将重复的结点都遍历过，然后将后面节点复制给pre结点后面
if(cur.next != null && cur.val == cur.next.val){
while(cur.next != null &&cur.val == cur.next.val){
cur = cur.next;
}
pre.next = cur.next;
cur = cur.next;
}else{
pre = pre.next;
cur = cur.next;
}
}
return head.next;
}
}
</code></pre>
<ul>
<li>空间复杂度为 O(1) ，没有借助额外的空间</li>
<li>时间复杂度为 O(n) ，只遍历了⼀次链表</li>
</ul>
<h3 id="递归">递归</h3>
<p>将大问题分解为当前节点+剩余链表的子问题</p>
<pre><code class="language-java">/**
* 递归法：分治思想解决子问题
* 思路：将大问题分解为当前节点+剩余链表的子问题
*
*/
public class Solution {
public ListNode deleteDuplication(ListNode head) {
// 递归终止条件：空链表或单节点链表
if (head == null || head.next == null) {
return head;
}
// 情况1：当前节点与下一节点重复
if (head.val == head.next.val) {
// 跳过所有重复节点，找到第一个不重复的节点
ListNode node = head.next;
while (node != null && head.val == node.val) {
node = node.next;
}
// 递归处理剩余部分
return deleteDuplication(node);
}
// 情况2：当前节点不重复
else {
head.next = deleteDuplication(head.next);
return head;
}
}
}
</code></pre>
<ul>
<li>时间复杂度：O(n)</li>
<li>空间复杂度：O(n) ，递归栈空间</li>
</ul>
<h3 id="三指针法">三指针法</h3>
<p>使用pre、cur、next三个指针精确控制删除范围</p>
<pre><code class="language-java">public class Solution {
public ListNode deleteDuplication(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy; // 前驱指针
ListNode cur = head; // 当前指针
ListNode next = null; // 后继指针
while (cur != null && cur.next != null) {
next = cur.next;
// 发现重复节点
if (cur.val == next.val) {
// 移动next直到找到不重复的节点
while (next != null && cur.val == next.val) {
next = next.next;
}
// 跳过所有重复节点
pre.next = next;
cur = next;
}
// 没有重复，正常移动指针
else {
pre = cur;
cur = cur.next;
}
}
return dummy.next;
}
}
</code></pre>
<ul>
<li>时间复杂度：O(n)</li>
<li>空间复杂度：O(1)</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19411014
頁:
[1]