删除链表中重复的节点

在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5
解题方法:
1.遍历链表,将重复节点加入HashSet中,之后根据HashSet是否包含重复值进行去重,先删除根节点,再删除中间节点;
时间复杂度O(n),空间复杂度再好的情况下为O(1),最坏的情况下为O(n/2).
2.增加一个头节点的辅助节点,就不需要hashset了,cur的作用是去除重复的节点,当循环退出时,cur指向的还是重复节点,因此需要再向后移动一步.
时间复杂度O(n),空间复杂度O(1)

public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {
        if(pHead == null || pHead.next == null) return pHead;
        ListNode head = new ListNode(Integer.MIN_VALUE);
        head.next = pHead;    //创建辅助头节点
        ListNode pre = head, 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;   //循环退出时cur指向的还是重复节点,需要再往后移动一步
                pre.next = cur;
            }else{
                pre = cur;
                cur = cur.next;
            }
        }
        return head.next;
    }
}
上一篇:循环单链表及常用操作(C语言描述)


下一篇:C语言构建一个链表以及操作链表