数据结构与算法——Java实现 11.习题——有序链表去重
目录
82. 删除排序链表中的重复元素 II
方法1
方法2
要知道，每一颗钻石在被发现前，都要经受埋藏尘埃的寂寞时光
—— 24.9.23
82. 删除排序链表中的重复元素 II
给定一个已排序的链表的头
head， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。示例 1：
输入：head = [1,2,3,3,4,4,5] 输出：[1,2,5]示例 2：
输入：head = [1,1,1,2,3] 输出：[2,3]提示：
- 链表中节点数目在范围
[0, 300]内-100 <= Node.val <= 100- 题目数据保证链表已经按升序 排列
注意：重复元素一个不留
方法1
递归函数负责返回：从当前节点开始，完成去重的链表
1.若当前节点与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){ListNode x = head.next.next;while(x != null && x.val == head.val){x = x.next;}// 与p取值不同的节点return deleteDuplicates(x);}else{head.next = deleteDuplicates(head.next);return head;}}
}
方法2
非递归、一次遍历实现
建立三个指针，指针1指向哨兵节点，指针2和指针3指向第一、二个节点，如果指针2和指针3指向的节点相同，则将他们删去，如果指针2和指针3指向的元素不相等，则将指针2、3都往后移动一位，知道指针3指向为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 s = new ListNode(-1, head);ListNode node = s;while (node.next != null && node.next.next != null){if (node.next.val == node.next.next.val){int x = node.next.val;while(node.next != null && node.next.val == x){node.next = node.next.next;}}else{node = node.next;}}return s.next;}
}