删除有序链表中的重复元素(LeetCode83. 删除排序链表中

题目

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

解题思路

1. 有序链表遍历到的当前节点，只需要判断与其前驱节点值是否相同就可以，所以定义变量preValue记录前一个节点的值，每次遍历更新。
2. 如果与preValue相同，代表当前节点重复，更新preValue，继续遍历下一个节点。
3. 如果与preValue不同，代表不重复节点，需要加入到新的链表中，更新preValue，继续遍历下一个节点。
4. 新链表定义一个头节点，两个指针分别为头指针和尾指针。加入到新链表的节点，需要将其next指针置null，切断与原有链表的联系。这样返回新的头节点就是新链表的所有节点。

代码

public ListNode deleteDuplicates(ListNode head) {
    if(null == head){
        return null;
    }
    //定义新链表的头节点
    ListNode newHead = new ListNode(0);
    ListNode newTail = newHead;
    //初始化preValue为第一节点的值键1即可，保证第一个节点可以被放入新链表中
    int preValue = head.val - 1;
    //遍历链表的节点
    while(head != null){
        //如果当前节点val与preValue不相等，不重复节点
        if(head.val != preValue){
            //放入新的链表中
            newTail.next = head;
            newTail = head;
        }
        //无论是否是重复节点，都需要更新preValue，并且继续遍历下一个节点
        preValue = head.val;
        head = head.next;
        //新链表的尾指针的next置为null
        newTail.next = null;
    }
    return newHead.next;
}