美文网首页
面试题19-删除链表中重复的节点

面试题19-删除链表中重复的节点

作者: 小庄bb | 来源:发表于2017-09-06 11:09 被阅读28次

    题目要求

    删除链表中重复的节点。
    重复的节点:
    当前节点的值与下一个节点的值相等,那么称这两个节点为重复的节点

    题目解析

    思路一:

    • 分析

    假设该链表为2、3、3、4、4、5
    删除完毕之后变为2、5
    那么如果是2、2、5、6
    删除完毕之后成为5、6。这个时候需要改变头结点,所以我们必须返回新的头结点
    另外还需要考虑的是如果是2、2、2
    那么删除完毕之后,链表为空。
    情况分析完毕,现在我们来看如何对重复的节点进行删除。
    首先从头结点开始遍历,检查当前节点的值curValue是否与下一个节点的值相等。如果相等继续检查再下一个节点是否相等。
    直到发现不相等的,将最后一个相等的节点的next值赋给第一个相等的节点的上一个节点的next。
    如果head节点就是相等的节点,那么我们在删除以后要注意改变链表的头结点。

    • 代码段
    public static ListNode deleteRepeatNode(ListNode head) {
            
            //定义一个辅助节点记录删除区间的前一个节点
            ListNode preNode = null ;
            //定义一个辅助节点记录头结点
            ListNode headNode = head ;
            //定义一个辅助标记是否有重复的节点
            boolean hasRepeat = false ;
            
            //判空
            if(head == null) {
                return headNode ;
            }
            
            
            //从head开始往尾节点遍历
            while( head != null && head.getNext() != null) {
                
                //遍历有多少个重复的节点
                while( head.getNext() != null && head.getValue() == head.getNext().getValue()) {
                    head = head.getNext() ;
                    hasRepeat = true ;
                }
                
                if (hasRepeat) {
                    //如果存在了重复的节点,那么进行删除处理
                    if(preNode == null) {
                        headNode = head.getNext() ;
                    }else {
                        preNode.setNext(head.getNext());
                    }
                }else {
                    //如果不存在,记录当前不存在的节点,作为preNode ;
                    preNode = head ;
                }
                
                head = head.getNext() ;
                
            }
            
            return headNode ;
        }
    

    测试代码

    public static void main(String[] args) {
            
            ListNode node1 = new ListNode() ;
            ListNode node2 = new ListNode() ;
            ListNode node3 = new ListNode() ;
            ListNode node4 = new ListNode() ;
            ListNode node5 = new ListNode() ;
            ListNode head = null ;
            
            node1.setValue(1);
            node2.setValue(1);
            node3.setValue(3);
            node4.setValue(3);
            node5.setValue(5);
            
            node1.setNext(node2);
            node2.setNext(node3);
            node3.setNext(node4);
            node4.setNext(node5);
            
            head = deleteRepeatNode(node1) ;
            showListNode(head);
            
            node1.setValue(1);
            node2.setValue(2);
            node3.setValue(3);
            node4.setValue(4);
            node5.setValue(5);
            
            node1.setNext(node2);
            node2.setNext(node3);
            node3.setNext(node4);
            node4.setNext(node5);
            
            head = deleteRepeatNode(node1) ;
            showListNode(head);
            
            node1.setValue(1);
            node2.setValue(1);
            node3.setValue(1);
            node4.setValue(1);
            node5.setValue(1);
            
            node1.setNext(node2);
            node2.setNext(node3);
            node3.setNext(node4);
            node4.setNext(node5);
            
            head = deleteRepeatNode(node1) ;
            showListNode(head);
            
            ListNode nullNode = null ;
            head = deleteRepeatNode(nullNode) ;
            showListNode(head);
            
        }
    

    运行结果

    5
    1 2 3 4 5


    看完整源码戳源码地址

    相关文章

      网友评论

          本文标题:面试题19-删除链表中重复的节点

          本文链接:https://www.haomeiwen.com/subject/sxvmjxtx.html