Topic describes
There is a linked list in ascending order, and you are given the head node of the linked list. Please delete all the nodes in the linked list that have duplicate numbers, and only keep the original list that does not have duplicate numbers.
Returns a linked list of results, also in ascending order.
Answer key
[Leetcode] 83. Delete duplicate elements from a sorted list.
Delete all nodes with duplicate elements. We need three Pointers.
A Dumyhead is placed before head, pre points to Dummyhead, mid points to head, cur points to head. Next. Three Pointers, as always, if there are no duplicates between mid and cur, then the three Pointers move to the right.
If you find a duplicate, how do you delete it? Record the duplicate element, val, and move the cur pointer until it is not val. Mid follows cur and pre does not move. (If cur moves to null, it would be even better.
After that, the normal delete operation, setting mid to null, goes back to cur, disconnects the right side of the repeat sequence, disconnects the left side of the repeat sequence, and moves cur one more bit to the right to place the front, middle, and back Pointers.
Execution time: 0 ms, beating 100.00% of users in all Java commits
Memory consumption: 38.1 MB, beating 5.73% of all Java commits
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode deleteDuplicates(ListNode head) { if (head == null || head.next == null) return head; ListNode dummyHead = new ListNode(-1); dummyHead.next = head; ListNode pre = dummyHead; ListNode mid = head; ListNode cur = head.next; while (mid ! = null && cur ! = null) { if (mid.val ! = cur.val) { pre = pre.next; mid = mid.next; cur = cur.next; } else { int val = cur.val; while (cur ! = null && cur.val == val) { mid = mid.next; cur = cur.next; } if (cur == null) { pre.next = null; } else { // cur ! = null mid.next = null; mid = cur; cur = cur.next; pre.next = mid; } } } return dummyHead.next; }}Copy the code