76.md

删除链表中重复的结点

题目

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 进阶：空间复杂度 O(n)，时间复杂度 O(n)

示例

例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5

思路

在遍历单链表的时候，检查当前节点与下一点是否为相同值，如果相同，继续查找祥同值的最大长度，然后指针改变指向

实现

package main

type ListNode struct {
	Val  int
	Next *ListNode
}

// 删除链表中重复的结点
func main() {
	var pHead *ListNode
	for _, v := range [7]int{5, 4, 4, 3, 3, 2, 1} {
		node := ListNode{
			Val:  v,
			Next: pHead,
		}
		pHead = &node
	}
	deleteDuplication(pHead)
}

func deleteDuplication(pHead *ListNode) *ListNode {
	var vhead *ListNode = &ListNode{
		Val:  -1,
		Next: pHead,
	}
	var pre *ListNode = vhead
	var cur *ListNode = pHead
	for {
		if cur == nil {
			break
		}
		if cur.Next != nil && cur.Val == cur.Next.Val {
			cur = cur.Next
			for {
				if cur.Next == nil || cur.Val != cur.Next.Val {
					break
				}
				cur = cur.Next
			}
			cur = cur.Next
			pre.Next = cur
		} else {
			pre = cur
			cur = cur.Next
		}

	}
	return vhead.Next
}