删除链表中重复的节点

题目描述

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

解法一：

使用指针index指向链表头pHead，辅助指针current指向index之后第一个值不等于index.val的节点。若index指向的节点是无重复的，则index与current中间没有节点；若index与current之间还有别的节点，则index必定为重复节点。通过这种方式可以确定每个节点是否为重复节点，从而得到无重复链表。
增加一个头节点，可以有效解决初始节点为重复节点的问题。

public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {
        if (pHead == null || pHead.next == null)
            return pHead;
        if(pHead.next.next == null) {
            if(pHead.val == pHead.next.val)
                pHead = null;
            return pHead;
        }
        ListNode start = new ListNode(0);
        start.next = pHead;
        ListNode res = start;
        ListNode index = pHead;
        ListNode current = pHead.next;
        //记录index与current间是否存在节点
        boolean flag = false;
        while(current != null) {
            if(index.val == current.val) {
                current = current.next;
                flag = true;
            }
            else {
                if(flag == true) {
                    index = current;
                    current = current.next;
                    flag = false;
                }
                else {
                    start.next = index;
                    start = start.next;
                    index = index.next;
                    current = current.next;
                }
            }
        }
        if(flag == false)
            start.next = index;
        else
            start.next = null;
        return res.next;
    }
}

注意程序中高亮部分，由于当current == null时，index很可能仍未遍历到链表尾。我们知道，只要当index.val != current.val时，index便会跳转到current的位置，则循环结束时有三种可能：
1、index.val != current.val，且index与current之间没有节点。如1->2->3->4。index跳转末位置指向链表尾。flag = false。start链表没有添加index的末位置。
2、index.val != current.val，且index与current之间有节点。如1->2->3->3->4。index跳转末位置指向链表尾。flag = true。start链表添加了index的末位置。
3、index.val == current.val。如1->2->3->3。index末位置不指向链表尾巴。flag = true。start链表没有添加index的末位置。
所以需要高亮部分对新链表尾进行设置。

解法二：

XXXXXXXXXXX