删除排序链表中的重复元素 II
题目描述
给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中没有重复出现的数字。
示例
示例 1:
1 2
| 输入:1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5 输出:1 -> 2 -> 5
|
示例 2:
1 2
| 输入:1 -> 1 -> 1 -> 2 -> 3 输出:2 -> 3
|
题目来源:力扣(LeetCode)
题目链接:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii
题目著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解法一
直接定义三个指针来扫描这个链表。扫描过程要保存删除过的节点,遍历完成后要检查最后一个元素是否需要删除。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
|
class Solution { public ListNode deleteDuplicates(ListNode head) { if (head == null) return null; if (head.next == null) return head; ListNode root = new ListNode(0); root.next = head; Integer deleteValue = null;
ListNode lastNode = root; ListNode currentNode = head; ListNode nextNode = head.next;
while (nextNode != null) { if (deleteValue != null && deleteValue == currentNode.val) { lastNode.next = nextNode; currentNode = nextNode; if (currentNode == null) break; nextNode = currentNode.next; continue; } if (currentNode.val == nextNode.val) { deleteValue = currentNode.val; lastNode.next = nextNode.next; currentNode = lastNode.next; if (currentNode == null) break; nextNode = currentNode.next; } else { nextNode = nextNode.next; currentNode = currentNode.next; lastNode = lastNode.next; deleteValue = null; } } if (currentNode != null && deleteValue != null && deleteValue == currentNode.val) { lastNode.next = nextNode; } return root.next; } }
|
解法二
这是评论区中的一个人提出的解法,我觉得这个方法很妙,思路很清晰。
这个解法使用了双指针来记录重复元素的区间。
- 右指针不停向右移动,直到 left.value != right.value
- 然后根据 left 和 right 的距离来删除元素
- 接着将 left 指针移动到 right 的位置继续扫描
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
|
class Solution { public ListNode deleteDuplicates(ListNode head) { if (head == null) return head; ListNode dummy = new ListNode(-1); ListNode tail = dummy; for (ListNode l = head, r = head; l != null; l = r) { while (r != null && r.val == l.val) r = r.next; if (l.next == r) { tail.next = l; tail = l; tail.next = null; } } return dummy.next; } }
|