题目描述
在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5
思路
1.这道题的核心思想是跳过值重复的结点。
2.可以设置一个哑结点,防止链表中全部的值都是重复的。
3.可以设置两个值,分别用于标记当前结点是否重复。
4.整体流程就是:
- 进入循环
- 保存当前结点
- 循环跳过重复结点
- 判断当前结点是否移动过,若移动过,需要跳过
Java代码实现
class Solution { public int findMin(int[] array) { if(array.length == 0) return 0; int left = 0; int right = array.length - 1; while(left <= right){ int mid = (left+right)/2; if(array[mid] < array[0]){ if(mid > 0 && array[mid-1] > array[mid]){ return array[mid]; }else { right = mid - 1; } }else{ left = mid + 1; } } return array[0]; } }
Golang代码实现
func deleteDuplicates(head *ListNode) *ListNode { if head == nil || head.Next == nil{ return head } p := new(ListNode) res := p for head != nil { pre := head cur := head.Val for head.Next != nil && head.Next.Val == cur{ head = head.Next p.Next = nil } if pre != head{ head = head.Next continue } p.Next = head p = p.Next head = head.Next } return res.Next }