双指针

删除有序链表中重复出现的元素

http://www.nowcoder.com/questionTerminal/71cef9f8b5564579bf7ed93fbe0b2024

先定义一个头节点用于指示链表的头部位置,方便最后返回链表。
然后定义两个指针p和q,初始化时,p先指向头结点,q指向head,开始遍历链表,因为链表是有序的,所以重复元素一定是连续出现的,所以我的策略就是先找出重复的一段子链表,然后一网打尽,具体做法就是:
如果q.next.val != q.val时,就移动p和q;
如果q.next.val == q.val时,就不动p,然后移动q,移动到与当前重复子链表相邻的第一个元素(不与子链表中的元素相等),此时p位于重复子链表的左边相邻位置,q位于右边的相邻位置,将p的next指针指向q即可完成删除。

    public ListNode deleteDuplicates (ListNode head) {
        // write code here

        if (head == null || head.next == null){
            return head;
        }

        ListNode node = new ListNode();

        node.next = head;

        ListNode p = node;
        ListNode q = head;

        while (q != null && q.next != null){

            if (q.next.val != q.val){

                p = q;
                q = q.next;
            }else {

                while (q.next != null && q.val == q.next.val){
                    q = q.next;
                }
                q = q.next;
                p.next = q;
            }
        }

        return node.next;
    }
全部评论
思路清奇,秀!
点赞 回复 分享
发布于 2024-04-23 00:17 上海

相关推荐

02-25 16:55
已编辑
北京工业大学 Java
211本,找日常实习的话,如果面向中厂的话,需要刷hot100么?因为之前从来没刷过,算法仅限于学校课程水平,准备3月投递简历,现在还需要背八股文,时间有些紧张,还需要刷算法题么?同时什么样的公司可以算是中厂呢?
程序员小白条:中大厂说的上名字的,必定要算法,hot100只是最基础的了,题库远不止100题捏,一般在300-400题量之间,算法=学校课程=简单题也做不出,多准备八股文和算法吧,其他项目可以放放,精刷算法就行了,花时间成长很快的
点赞 评论 收藏
分享
评论
11
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务