给定一个排序链表, 删除所有重复的元素, 使得每个元素只出现一次.
示例 1:
输入: 1->1->2
输出: 1->2
示例 2:
输入: 1->1->2->3->3
输出: 1->2->3
链接: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list
- public class ListNode {
- int val;
- ListNode next;
- public ListNode(int val) {
- this.val = val;
- }
- }
解题思路:
1, 首先要知道, 链表是如何实现删除元素 -- 当前结点的 next 指针指向结点 A, 让其不指向 A 结点, 指向其他结点, 就实现了 A 结点的删除.
2, 当前结点和后一结点做比较, 如果两者值相等, 当前结点的 next 指针不指向与其值相等的下一结点, 而是指向下一结点的 next
如果不相等, 进行下一个结点和其 next 指针所指向结点的比较.
3, 利用链表的原理和递归的思想
代码 1,
- class Solution {
- public ListNode deleteDuplicates(ListNode head) {
- ListNode guardNode = new ListNode(0);
- ListNode newLinkedList = guardNode;
- if(head != null) {
- newLinkedList.next = head;
- int val = head.val;
- if (head.next != null) {
- if (head.val == head.next.val) {
- // 当前节点的 next 指针指向后一结点的 next 指针
- head.next = head.next.next;
- deleteDuplicates(head);
- } else {
- head = head.next;
- }
- }
- }
- return guardNode.next;
- }
- }
代码 2, 和代码 1 的核心思想是一样的, 只是优雅了一下代码. 执行用时均为 1ms, 但是内存消耗少了 0.2M
- class Solution {
- public ListNode deleteDuplicates(ListNode head) {
- if (head == null) {
- return null;
- }
- if (head.next == null) {
- return head;
- }
- if (head.val == head.next.val) {
- head.next = head.next.next;
- deleteDuplicates(head);
- } else {
- deleteDuplicates(head.next);
- }
- return head;
- }
- }
来源: http://www.bubuko.com/infodetail-3325885.html