题目

82. 删除排序链表中的重复元素 II

题解

代码

/** * Definition for singly-linked list. public class ListNode { int val; ListNode * next; ListNode(int x) { val = x; } } */

public class code82 {

    public static ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode slow = dummy;
        ListNode fast = dummy.next;
        while (fast != null) {
            while (fast.next != null && fast.val == fast.next.val) { // 用快指针跳过那些重复数字
                fast = fast.next;
            }
            if (slow.next == fast) { // 如果不存在重复元素的话
                slow = slow.next;
                fast = fast.next;
            } else { // 如果存在重复元素的话
                slow.next = fast.next;
                fast = fast.next;
            }
        }
        return dummy.next;
    }

    public static void print(ListNode node) {
        if (node == null) {
            return;
        }
        ListNode current = node;
        while (current != null) {
            System.out.print(current.val + " -> ");
            current = current.next;
        }
        System.out.println("NULL");
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(3);
        ListNode listNode5 = new ListNode(4);
        ListNode listNode6 = new ListNode(4);
        ListNode listNode7 = new ListNode(5);

        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        listNode5.next = listNode6;
        listNode6.next = listNode7;

        ListNode head = deleteDuplicates(listNode1);
        print(head);
    }
}

参考

1. 递归与非递归——题解一
2. 简单易懂，将链表转为数组，然后去掉重复元素，再转为数组——题解二
3. 【Leetcode】82. 删除排序链表中的重复元素 II
4. Leetcode 82:删除排序链表中的重复元素 II（最详细解决方案！！！）