删除链表中重复的节点

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表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;    }}

更多相关文章

随机推荐