剑指offer_删除链表中重复的节点

叁歲伎倆 2022-06-09 03:00 166阅读 0赞

/*
    在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 
    例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
    
    思路：
    遍历链表，判断当前结点的下一个结点是否与当前结点相同，
    若不相同则继续遍历下一个结点，
    若相同则找到下一个不相同的结点，中间的全部删除
    
    考虑头结点重复怎么办
    */
    
    class DeleteDuplication
    {
    	public static ListNode deleteDuplication(ListNode pHead)
    	{
    		if (pHead==null)
    		{
    			return null;
    		}
    
    		ListNode pTemp=pHead;
    
    		ListNode pre=null;//记录重复结点的前一个结点，用于删除，如果第一个结点就重复呢？
    		while (pTemp!=null&&pTemp.next!=null)
    		{
    			if (pTemp.val!=pTemp.next.val)//若未出现重复，继续遍历下一个
    			{
    				pre=pTemp;
    				pTemp=pTemp.next;
    			}else  //若出现重复，找到所有重复结点的最后一个，用pTemp表示
    			{
    				while (pTemp.next!=null&&pTemp.val==pTemp.next.val)
    				{
    					pTemp=pTemp.next;
    				}
    				
    				//pTemp指向重复结点之后的结点
    				pTemp=pTemp.next;
    
    				if (pre==null)//pre==null意味着链表开头部分都是重复，需要删除，需要更新头结点
    				{
    					pHead=pTemp;
    				}else	//pre!=null则直接删除
    					pre.next=pTemp;
    			}
    		}
    
    		return pHead;
    	}
    
    	public static void main(String[] args) 
    	{
    		ListNode head=new ListNode(1);
    		ListNode node1=new ListNode(1);
    		ListNode node2=new ListNode(1);
    		ListNode node3=new ListNode(1);
    		ListNode node4=new ListNode(3);
    		ListNode node5=new ListNode(4);
    
    		head.next=node1;
    		node1.next=node2;
    		node2.next=node3;
    		node3.next=node4;
    		node4.next=node5;
    
    		head=deleteDuplication(head);
    
    		while (head!=null)
    		{
    			System.out.println(head.val);
    			head=head.next;
    		}
    		
    	}
    }