数据结构与算法——Java实现 10.习题——删除有序链表重复节点
所有无能为力的事情，我都在慢慢接受
—— 24.9.22
83. 删除排序链表中的重复元素
给定一个已排序的链表的头
head， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。示例 1：
输入：head = [1,1,2] 输出：[1,2]示例 2：
输入：head = [1,1,2,3,3] 输出：[1,2,3]提示：
- 链表中节点数目在范围
[0, 300]内-100 <= Node.val <= 100- 题目数据保证链表已经按升序 排列
注意：重复元素保留一个
方法1
思路
给链表设置两个指针，因为链表已排序，比较两个指针指向的元素是否相等，如果两指针指向的元素相等，则删除指针2，指针1此时保持不变
指针1指向的元素不等于指针2指向的元素，则指针1，指针2同时向后移动一位
当指针2指向元素为null时，退出循环
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode deleteDuplicates(ListNode head) {if (head == null || head.next == null) {return head;}ListNode p1 = head;ListNode p2;while((p2 = p1.next)!=null){if(p2.val==p1.val){p1.next = p2.next;}else{p1 = p2;}}return head;}
}
方法2
递归函数负责返回：从当前节点开始，完成去重的链表
1.若当前节点与next重复，返回next节点
2.若当前节点与next不重复，返回当前节点，但next的值进行更新
递归函数返回的是每个结点的去重结果，递归到最深一层，将所有节点的重复结果都删去，剩下返回的是去重后的链表
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode deleteDuplicates(ListNode head) {if (head == null || head.next == null) {return head;}if (head.val == head.next.val) {return deleteDuplicates(head.next);}else{head.next = deleteDuplicates(head.next);return head;}}
}