[Link] https://leetcode.com/problems/remove-duplicates-from-sorted-list/
Approach
Because the list is sorted, equal values are adjacent. Keep a pointer at the last retained node. If its next node has the same value, bypass that next node; otherwise, advance the pointer. At each step, the list from the head through the pointer contains exactly one node for every distinct value processed so far, in sorted order. The final retained node is the original last node, whose next is already null, so the result has no cycle.
Each node is examined once, so the time complexity is O(N). The algorithm reuses the input nodes and uses O(1) extra space.
/**
* 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) {
ListNode node = head;
while (node != null && node.next != null) {
if (node.val == node.next.val) {
node.next = node.next.next;
} else {
node = node.next;
}
}
return head;
}
}