《剑指offer》 第18.2题 删除链表的节点之删除重复节点

题目描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

解法1：

  如果链表中要删除某个节点，我们需要找到这个节点的前一个节点，否则在删除时会断开。因此使用一个pre来记录之前的节点。
过程：在寻找过程中，我们肯定是比较当前的节点和当前节点的下一个节点的值。
  这里举例2-3-4-5-5-5-5-6-6-7。pre应该记录4，而cur应当直到了6，然后进行处理。特殊情况是头结点会重复。因此也要拿出来处理。具体分析过程在代码的注释中了。
  这里没有使用虚拟头结点或者辅助头结点。如果用了虚拟头结点的话，下面的判断是不是头节点重复的步骤可以省略，少两行代码。但是最后需要返回的是虚拟头结点的next，才是真实的头结点。

public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {
        ListNode pre = null;//头结点的前驱是Null
        ListNode cur = pHead;
        while(cur!=null){
            if(cur.next!=null && cur.next.val==cur.val){//相等时
                while(cur.next!=null && cur.next.val==cur.val)
                    cur=cur.next;//我们要找下一个不重复的，防止某个节点出现了3次或者更多
//以2-3-4-5-5-5-5-6-6-7而言，此时cur指向了5，而cur.next是6，因此我们再移动，让cur指向6
                cur=cur.next;
                if(pre==null)//这两行是对头结点重复的处理，更新头节点（如2-2-2-3-4-5）
                    pHead=cur;
                else//如果不是重复的节点，就是常规的重复，就将4和6连接起来。
                    pre.next=cur;
            }else{//此时是不相等，相应的进行移动
                pre=cur;
                cur=cur.next;
            }
        }
        return pHead;
    }
}

虚拟头结点的写法

public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {
        if(pHead==null) return null;
        // 构建辅助头结点
        ListNode head = new ListNode(Integer.MIN_VALUE);//保证赋值和任何节点值都不重复
        head.next = pHead;
        ListNode pre = head;
        ListNode cur = head.next;
        while(cur!=null){
            if(cur.next != null && cur.next.val == cur.val){
                while(cur.next != null && cur.next.val == cur.val){
                    cur = cur.next;
                }
                cur = cur.next;
                pre.next = cur;
            }else{
                pre = cur;
                cur = cur.next;
            }
        }
        return head.next;//虚拟头结点的next才是真实头结点
    }
}

解法2：

递归，不用考虑头结点的情况。

public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        if (pHead == null || pHead.next == null) { 
            return pHead;
        }
        if (pHead.val == pHead.next.val) { // 当前节点是重复节点
            ListNode node = pHead.next;
            while (node != null && node.val == pHead.val) {
                // 跳过值与当前节点相同的全部节点，找到第一个与当前节点不同的节点
                node = node.next;
            }
            // 从不重复的结点继续递归，并且这个节点也是上次递归的返回值
            return deleteDuplication(node); 
        } else {
            //继续递归下一个节点。返回的是不重复的节点，因此直接连起来就好
            pHead.next = deleteDuplication(pHead.next); 
            return pHead;
        }
    }
}

总结：

  一刚开始也想过用TreeSet，不过想来想去，还是用正统的解法吧。毕竟本题考察的就是去重这一过程，使用Set太虚了，在面试的时候不讨好。本题递归的写法，在链表重复元素较少时，性能比较低。对于我个人来说，解法1比递归容易看懂，总之就是推荐掌握解法1.