删除链表中的重复元素

题目描述

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

测试用例

用例一

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

用例二

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

实现方案

递归实现

• 因为题目给出的是已排序的数组，则重复元素必然连续，故一次处理即可删除重复元素
• 如果 head == nil 或者 head.Next == nil 则直接返回head即可
• 如果 head.Val != head.Next , 则 head.Next = deleteDuplicates(head) , 向后迭代即可
• 如果 head.Val != head.Next, 则一直向后移动指针move, 直至 head.Val != move.Val 为止, 并返回 deleteDuplicates(head)

// ListNode Definition for singly-linked list.
type ListNode struct {
    Val int
    Next *ListNode
}

func deleteDuplicates(head *ListNode) *ListNode {
  if nil == head {
    return nil
  }
  if nil == head.Next {
    return head
  }
  if head.Next.Val != head.Val {
    head.Next = deleteDuplicates(head.Next)
  } else {
    // 相等. 直到找到不相等的位置
    move := head.Next
    for move != nil && move.Val == head.Val {
      move = move.Next
    }
    return deleteDuplicates(move)
  }
  return head
}

迭代实现

小技巧 -> 哑节点 :
要对头结点进行操作时，考虑创建哑节点dummy，使用dummy->next表示真正的头节点。这样可以避免处理头节点为空的边界问题。

• 新建哑节点, 作为头节点, 降低 对头节点操作的复杂度, 最终返回 dummy.Next 即可
• 开始迭代, 若当前节点下一个节点和下下一个节点值相等，记录当前值为待比较的值。
• 指针后移, 反复修改当前节点的Next指向, 直至当前节点值下一个节点值和待比较值不一致
• 若当前节点下一个节点和下下一个节点值不想等, 当前节点直接设置为 cur.Next , 无需变更指针指向关系

func deleteDuplicates(head *ListNode) *ListNode {
  dummy := &ListNode{
    Val:  0,
    Next: head,
  }
  cur := dummy
  for cur.Next != nil && cur.Next.Next != nil {
    if cur.Next.Val == cur.Next.Next.Val {
      compareVal := cur.Next.Val
      for cur.Next != nil && cur.Next.Val == compareVal {
        cur.Next = cur.Next.Next
      }
    } else {
      cur = cur.Next
    }
  }
  return dummy.Next
}

1. 题目原地址-leetcode-82-删除重复元素 ↩