Leetcode83.删除排序链表中的重复元素

1.题目

给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。

示例 1:

输入: 1->1->2
输出: 1->2
示例 2:

输入: 1->1->2->3->3
输出: 1->2->3

2.解答

首先我的思路就是使用两个相邻变量p,q,从头节点开始向后进行遍历,如果二者的值相等,那么修改两个节点的指针,知道最后的q != null的边界条件

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null)    return null;
        ListNode p = head,q = p.next;
        if(q == null)   return head;
        while(q != null){            
                if(p.val == q.val){
                    q = q.next;
                    p.next = q;
                }
                else{
                    p = p.next;
                    q = q.next;
                }            
        }
        return head;
    }
}

刚才优点尴尬,刚做出来题就黏黏自喜的,就开始得意忘形了啊,苏不知这是做题的大忌啊,其实,这道题使用一个变量就可以做出来的,,,,

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null)    return null;
        ListNode p = head;
        while(p.next != null){
            if(p.val == p.next.val){
                p.next = p.next.next;
            }
            else
                p = p.next;
        }
        return head;
    }
}

不管是哪种方法,按照题解中一个网友说的,可能会存在野指针的问题,在第一个代码中可以加上q == null,在第二个代码中可以先保存重复节点,然后进行释放,但是其实在Java语言中是不需要这种操作的,考虑的周全是一件好事,在JVM里面,如果没有被GC Roots引用到的对象,都会被垃圾收集器回收的。