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

原创
2016/06/29 14:22
阅读数 64

题目

在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5

解题


class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {
        if(pHead==null || pHead.next ==null)
            return pHead;

        ListNode preNode = null;
        ListNode pNode = pHead;
        while(pNode!=null){
            ListNode nextNode = pNode.next;
            boolean needDelete = false;
            // 找到删除结点
            if(nextNode!=null&&nextNode.val==pNode.val){
                needDelete = true;
            }
            if(!needDelete){// 不需要删除
                preNode = pNode; // 更新前驱节点
                pNode = pNode.next; // 当前结点后验
            }else{ // 需要删除
                int value = pNode.val; // 删除结点的值
                ListNode toBeDel = pNode; // 找到下一个不需要删除结点
            while(toBeDel!=null&&toBeDel.val == value){
                    nextNode = toBeDel.next;
                    toBeDel = nextNode;   
                }
            if(preNode==null)
                pHead = nextNode;
            else
                preNode.next = nextNode;
            pNode = nextNode;
          }
        }

        return pHead;
    }
}

 

展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部