删除链表中重复的结点 --剑指offer


题目描述

在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5   一:没参考写的 遇到相同的就删除 考虑多种情况 比较复杂
public class Solution {
    public static ListNode deleteDuplication(ListNode pHead)
    {
        if(pHead == null )return null;
        ListNode laseNode=null;
        int tem=0;
        ListNode p=pHead;
        boolean flag=false;
        while (p.next != null){
            if(p.val == p.next.val){
                int a=p.val;
                flag=true;
                if(laseNode == null){
                    pHead = p.next.next;
                    p=pHead;

                }else {
                    laseNode.next=p.next.next;
                    p=laseNode.next;
                }
                tem=a;
            }else if(p.val == tem && flag){
                laseNode.next=p.next;
                p=laseNode.next;
            }else {
                laseNode=p;
                p=p.next;
            }
            if(p==null) break;
        }
        if(p != null && p.val == tem && flag) {
            if(laseNode != null) {
                laseNode.next = p.next;
            }else {
                return null;
            }
        }
        return pHead;
    }

}

二:参考后写的

建立一个头结点 然后两个指针 找不相同的结点 相同的结点跳过

public class Solution {
    public static ListNode deleteDuplication(ListNode pHead){
        if (pHead == null || pHead.next == null)return pHead;
        ListNode node = new ListNode(0);
        node.next=pHead;
        ListNode p1=node,p2=pHead;
        while (p2 != null){
            while (p2.next!=null && p2.next.val == p2.val){
                p2 = p2.next;
            }
            if(p1.next != p2){
                p2=p2.next;
                p1.next=p2;
            }else {
                p1=p2;
                p2=p2.next;
            }
        }
        return node.next;
    }
}

 

上一篇:剑指offer-(3) 删除链表中重复的结点


下一篇:剑指offer第55题:链表中环的入口结点