力扣83. 删除排序链表中的重复元素

Problem: 83. 删除排序链表中的重复元素

题目描述

思路

1.定义快慢指针fast、slow均指向head；
2.每次fast后移一位，当fast和slow指向的节点值不一样时，将slow.next指向fast同时使slow指向fast；
3.去除链表尾部重复元素：最后判断slow是否指向fast，若没有则slow及其后面的元素均是重复的，直接使得slow.next为空即可

复杂度

时间复杂度:

$O(n)$;其中$n$是链表的原始长度

空间复杂度:

$O(1)$;

Code

/**
 * 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 {
    /**
     * Remove Duplicates from Sorted List
     *
     * @param head The head node of sorted linked list
     * @return ListNode
     */
    public ListNode deleteDuplicates(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null) {
            if (slow.val != fast.val) {
                slow.next = fast;
                slow = fast;
            }
            fast = fast.next;
        }
        //Determine if there are any duplicate elements at the end
        if (slow != fast) {
            slow.next = null;
        }
        return head;
    }
}