LeetCode CodeTop 82.删除排序链表中的重复元素Ⅱ

1.思路：两个指针分别指向cur.next和cur.next.next，如果发现重复就一次性删除所有值为val的节点；否则cur正常前进一位。

2.复杂度分析：

（1）时间复杂度：O(n)，其中n为链表的长度。

（2）空间复杂度：O(1)，仅用到若干额外变量。

附代码：

class Solution { public ListNode deleteDuplicates(ListNode head) { ListNode sentinel = new ListNode(); sentinel.next = head; ListNode cur = sentinel; while(cur.next != null && cur.next.next != null){ int val = cur.next.val; // 后两个节点值相同，都为val if(val == cur.next.next.val){ // 从第一个值等于val的节点开始，将值等于val的节点全部删除 while(cur.next != null && cur.next.val == val){ cur.next = cur.next.next; } }else{ cur = cur.next; } } return sentinel.next; } }

ACM模式：

import java.util.Scanner; // 将 ListNode 定义为独立的类 class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; this.next = null; } } public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 读取链表长度 int n = scanner.nextInt(); // 读取链表元素 int[] nums = new int[n]; for (int i = 0; i < n; i++) { nums[i] = scanner.nextInt(); } // 创建链表 ListNode head = null; if (n > 0) { head = new ListNode(nums[0]); ListNode current = head; for (int i = 1; i < n; i++) { current.next = new ListNode(nums[i]); current = current.next; } } // 调用删除重复元素方法 Solution solution = new Solution(); ListNode result = solution.deleteDuplicates(head); // 输出删除重复后的链表 if (result == null) { System.out.println(""); } else { ListNode current = result; while (current != null) { System.out.print(current.val); if (current.next != null) { System.out.print(" "); } current = current.next; } System.out.println(); } scanner.close(); } } // 删除重复元素方法放在 Solution 类中 class Solution { public ListNode deleteDuplicates(ListNode head) { ListNode sentinel = new ListNode(); sentinel.next = head; ListNode cur = sentinel; while (cur.next != null && cur.next.next != null) { int val = cur.next.val; // 后两个节点值相同，都为val if (val == cur.next.next.val) { // 从第一个值等于val的节点开始，将值等于val的节点全部删除 while (cur.next != null && cur.next.val == val) { cur.next = cur.next.next; } } else { cur = cur.next; } } return sentinel.next; } }