首页 计算机学科 java 编程题

# 删除排序链表中的重复元素

题目要求：

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

示例 1：

img

输入：head = [1,1,2]
输出：[1,2]

示例 2：

img

输入：head = [1,1,2,3,3]
输出：[1,2,3]

提示：

  • 链表中节点数目在范围 [0, 300] 内
  • -100 <= Node.val <= 100
  • 题目数据保证链表已经按升序 排列

# 方法 1：双指针

p1   p2
1 -> 1 -> 2 -> 3 -> 3 -> null
  • p1.val == p2.val 那么删除 p2，注意 p1 次时保持不变
p1   p2
1 -> 2 -> 3 -> 3 -> null
  • p1.val != p2.val 那么 p1，p2 向后移动
p1   p2
1 -> 2 -> 3 -> 3 -> null
p1   p2
1 -> 2 -> 3 -> 3 -> null
  • p1.val == p2.val 那么删除 p2
p1   p2
1 -> 2 -> 3 -> null

代码：

public ListNode deleteDuplicates(ListNode head) {
      if(head == null)
      {
        return head;
      }
      ListNode p1 = head;
      ListNode p2;
      //p1 前指针 p2 后指针 两个指针 同时向后移动
      while((p2 = p1.next) != null)
      {
        // 判断 前后 两个 val 是否相同
        if(p1.val == p2.val)
        {
          // 相同则删除
          p1.next = p2.next;
        }else
        {
          // 如果不相同就移动 p1 指针
          p1 = p1.next;
        }
      }
      return head;
    }