【剑指offer】面试题18：删除链表中重复的节点

浅浅的花香味﹌ 2022-06-12 09:26 200阅读 0赞

## 完整代码地址 ##

[完整代码地址][Link 1]

## 题目 ##

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

## 思路 ##

1.用tmpNode和current指向头结点，用一个flag标志遇到连续的重复值  
2.current用来遍历整个链表，在遍历时，每当遇到一个新的值的节点，就用tmpNode指向整个节点  
3.直到遇到下一个新的值前，current遍历链表，若有相同的值，flag置为false  
4.遇到下一个新的值时，若flag为true，则tmpNode没有重复；若flag为false，则tmpNode重复了  
5.遍历结束后还要在判断一次

**例子：**  
例如，链表1->2->3->3->4->4->5 处理后为 1->2->5  
1.tmpNode和current指向1  
2.current遍历到2，flag为true，1则加入新的链表中，tmpNode指向2  
3.current遍历到3，flag为true，2则加入新的链表中，tmpNode指向3  
4.current遍历到第二个3，遇到重复值，flag置为false  
5.current遍历到4，flag为false，3这个节点就不管了，flag重新置为true，tmpNode指向4  
6.current遍历到第二个4，遇到重复值，flag置为false  
7.current遍历到5，flag为false，4这个节点就不管了，flag重新置为true，tmpNode指向5  
8.遍历结束，做最后一次判断，flag为true则将5加入新的链表中（若为false则把最后一个节点的next指向null）

## 代码 ##

/**
     * 题目：
     * 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 
     * 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
     * 
     * @author peige
     */
    public class _18_02_DeleteDuplicatedNode {
        
    
        public static class ListNode {
        
            public int val;
            public ListNode next = null;
            public ListNode(int val) {
                this.val = val;
            }
        }
    
        public static ListNode deleteDuplication(ListNode pHead)
        {
            if(pHead == null || pHead.next == null)
                return pHead;
    
            ListNode newHead = new ListNode(0);
            ListNode node = newHead;
            boolean flag = true;
    
            ListNode tmpNode = pHead;
            ListNode current = pHead;
    
            while((current = current.next) != null) {
                if(current.val == tmpNode.val) {
                    flag = false;
                }
                // 之前没有重复元素
                else if(flag == true) {
                    node.next = tmpNode;
                    node = node.next;
                    tmpNode = current;
                }
                // 之前有重复元素
                else {
                    tmpNode = current;
                    flag = true;
                }
            }
            if(flag == true)
                node.next = tmpNode;
            else 
                node.next = null;
            return newHead.next;
        }
    }

## 测试 ##

public static void main(String[] args) {
        test1();
        test2();
        test3();
    }
    
    /**
     * 功能测试
     */
    private static void test1() {
        // 1-2-5
        ListNode head1 = createListNode(1,2,3,3,4,4,5);
        head1 = _18_02_DeleteDuplicatedNode.deleteDuplication(head1);
        printListNode(head1);
    
        // 7 
        ListNode head2 = createListNode(6,6,6,6,6,7);
        head2 = _18_02_DeleteDuplicatedNode.deleteDuplication(head2);
        printListNode(head2);
    }
    
    /**
     * 边界测试
     * 1.全是重复元素
     * 2.没有重复元素
     * 3.只有一个元素
     */
    private static void test2() {
        // null
        ListNode head1 = createListNode(6,6,6,6,7,7,7,8,8);
        head1 = _18_02_DeleteDuplicatedNode.deleteDuplication(head1);
        printListNode(head1);
    
        // 1-2-3-4-5
        ListNode head2 = createListNode(1,2,3,4,5);
        head2 = _18_02_DeleteDuplicatedNode.deleteDuplication(head2);
        printListNode(head2);
    
        // 1
        ListNode head3 = createListNode(1);
        head3 = _18_02_DeleteDuplicatedNode.deleteDuplication(head3);
        printListNode(head3);
    }
    
    /**
     * 极端测试
     * 1.头结点为null
     */
    private static void test3() {
        // null
        ListNode head1 = _18_02_DeleteDuplicatedNode.deleteDuplication(null);
        printListNode(head1);
    }
    
    private static void printListNode(ListNode head) {
        ListNode cur = head;
        while(cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    
    private static ListNode createListNode(int... values) {
        ListNode head = new ListNode(0);
        ListNode cur = head;
        for(int val : values) {
            cur.next = new ListNode(val);
            cur = cur.next;
        }
        return head.next;
    }

[Link 1]: https://github.com/linpeiyou/CodingInterviews