【剑指offer】删除链表中重复的节点

说实话这题看着简单，真的不简单啊，尤其是它是一个链表，不是数组，指向这指向那，晕死掉了...真的写不出来啊！

// 递归写法，比较容易理解，但当链表基本无重复节点时，效率不高。

public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        if (pHead == null || pHead.next == null) { // 只有0个或1个节点
            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;
        }

    }
}

// 非递归写法，要处理一个很棘手的问题：当头结点重复的时候，删除头结点。（脑壳疼）
// c/c++方法：参数声明为ListNode** pHead或者新建头结点。
// java方法:新建头结点。

public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        if (pHead == null || pHead.next == null) {
            return pHead;
        }

        ListNode head = new ListNode(-1); // 新建一个头结点，防止链表中头结点是重复节点被删除。
        ListNode trail = head;

        while (pHead != null) {
            ListNode node = pHead.next;
            boolean flag = false;
            while (node != null && pHead.val == node.val) {
                node = node.next;
                flag = true;
            }
            if (!flag) {
                trail.next = pHead;
                trail = trail.next;
            }
            pHead = node;
        }
        trail.next = null; // 1->2->3->3->3
        return head.next;
    }
}