–
layout: post
title: 删除链表中重复的结点
subtitle:
date: 2017-07-25
author: DH
header-img: img/post-bg-alibaba.jpg
catalog: true
tags:
- 算法
- 剑指offer
—
题目
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
分析
设置三个指针，first.next指针始终指向链表的开头,这样不管phead如何变化我们都能知道链表的开头。
last指针始终指向上一次搜索开始的地方，当搜索结束，找到不同的元素的时候，以便设置；
phead是一个活动指针。
（1）两两比较，如果phead和phead.next相同，那么有可能接下来连续的数都是相同的；我们的任务就是找到这个结尾
（2）找到一连串相同的节点的结尾；
（3）设置last.next 指向下一个不同的节点；
（4）如果下一个节点不相同，直接last和phead后移
代码
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode deleteDuplication(ListNode pHead)
{
if (pHead == null) {
return null;
}
// 设置一个节点指向头结点
ListNode firstNode = new ListNode(Integer.MIN_VALUE);
firstNode.next = pHead;
// last指针永远指向移动前的扫到的最后一个节点
ListNode lastNode = firstNode;
while (pHead != null && pHead.next != null) {
if (pHead.val == pHead.next.val ) {
int val = pHead.val;
while (pHead != null && pHead.val == val) {
pHead = pHead.next;
}
lastNode.next = pHead;
}else {
lastNode = pHead;
pHead = pHead.next;
}
}
return firstNode.next;
}
}
