Leetcode 83：Remove Duplicates from Sorted List

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

说人话：

去掉有序链表中重复的元素

要点：

• 链表
• 有序
• 去重复

举例：

[法1] 穿针引线

思路

因为链表本身是有序的，所以下一个节点 next 和当前节点 cur 只可能有 < = > 这三种关系。利用这个特性我们可以建立 2 个指针：

• cur：当前节点
• next：下一个节点

穿针引线的过程中，我们不断比较 cur 和 next 节点上值的关系

• 如果不等，那么直接穿针引线
• 如果相等，就删除掉 next 节点（cur.next = cur.next.next）

直到遍历完链表，也就实现了去重

代码

/**
 * 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 cur = head;

        while(cur != null){
          	//下一个节点
            ListNode next = cur.next;
          	//没有下一个节点的时候就结束了
            if(next == null){
                break;
            }
            //不相等，继续穿针引线
            if(cur.val != next.val){
                cur = next;
            }else{
                //相等，那么删除掉后面的元素
                cur.next = next.next;
            }

        }
        return head;
    }
}

提交结果

代码分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)