有序链表删除重复的节点，只保留不重复的节点

11月3日面试题

题目

有序链表删除重复的节点，只保留不重复的节点。
例如：链表1->2->2->3 ，结果：1->3

解析

O(n)时间复杂度遍历一次链表，首先定义新链表的头结点和尾节点，用于接收保留下的不重复的节点。

定义两个头尾指针遍历原有的链表，移动尾指针到与头指针节点值不相等的节点，如果尾指针与头指针的节点值相等，继续遍历，直到不相等。此时头指针和尾指针之间的节点就是“重复”的节点，如果头尾指针“挨着”，那么头指针的节点就是不重复的，如果不“挨着”，则头指针到尾指针之间的节点都是重复的。

更新头指针指向尾指针的节点，重复上面的步骤移动尾指针，直到链表全部遍历完。

如下示意图：

头尾指针移动示意图

代码

class Node{
    int val;
    Node next;
    public Node(){}
    public Node(int val, Node next){
        this.val = val;
        this.next = next;
    }
}

public Node removeDuplicatedElements(Node root){
    if(null == root || root.next == null){
        return root;
    }
    //新链表的头尾节点
    Node newHead = new Node(0, null);
    Node newTail = newHead;
    //定义尾指针
    Node tail = root.next;
    while(tail != null){
        //尾指针指向第一个与头指针不相等的节点
        while (tail != null && root.val == tail.val){
            tail = tail.next;
        }
        //如果头尾指针“挨着”，加入到新链表中
        if (root.next == tail){
            newTail.next = root;
            newTail = root;
            newTail.next = null;
        }
        //更新头指针指向尾指针节点，继续遍历
        root = tail;
    }
    return newHead.next;
}