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

youzhihua · · 521 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

第一次，站长亲自招 Gopher 了>>>

题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表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

}

有疑问加站长微信联系（非本文作者）