删除单链表中重复节点

引用：原文链接：https://blog.csdn.net/dadajixxx/article/details/87551738

/*题目
* 在一个排序的链表中，存在着重复的节点，请删除该链表中重复的节点，重复的节点不保留，返回链表头指针
* 示例1：1 -> 2 ->  2 ->  3 ->  3 ->  4 ->  5      -------->删除后： 1 ->  4 ->  5

* 示例2： 1->1->1->2->3      --------->删除后：2->3

 * 

* */

解法1：

/*思路
* 遍历节点的同时判断当前节点与下一个节点是否相同，如果相同则删除，
* 删除方法 使用相同节点的前一个节点，指向相同节点的下一个节点如图
*
* */

public class offer57 {

　　class ListNode{
　　　　int val;
　　　　ListNode next=null;
　　　　public ListNode(){ }
　　　　public ListNode(int val){
　　　　this.val=val;
　　　　}
　　}

public ListNode deleteDeplication(ListNode pHead){

　　if (pHead == null)  return null;

　　//注意备用头结点，头结点可能被删除
　　ListNode first = new ListNode(-1);

　　first.next = pHead;
　　ListNode p = pHead;
　　//前节点
　　ListNode preNode = first;

　　while (p != null && p.next != null){
　　　　if (p.val == p.next.val){ //两节点相等

　　　　　　int val = p.val; //记录val用于判断后面节点是否重复
　　　　　　while(p != null && p.val == val){ //这一步用于跳过相等的节点，用于删除
　　　　　　　　p = p.next;
　　　　　　}
　　　　　　preNode.next = p; //删除操作，前节点的next直接等于现在的节点，把中间的节点直接跨过
　　　　}else {
　　　　　　preNode = p;
　　　　　　p = p.next;
　　　　}
　　}
　　return first.next;
　　}
}

解法2：双指针法(也可以说是三指针法，设置的头结点需要参与元素链接，最后还需要输出) 设置一个新的头结点，使得链表元素进行链接和输出 当前后两个指针相同时，移动下一个指针到两个元素不相同，然后使用设置的头结点进行链接，得以越过相同元素 如果两个指针不相同，就移动处理，指针跟随

class Solution {
　　public ListNode deleteDuplicates(ListNode head) {
　　　　if(head == null || head.next == null) return null;

　　　　ListNode dummy = new ListNode(-1); //为链表创建一个新的头，return dummy.next 来带领整个链表
　　　　dummy.next = head;
　　　　ListNode current = head;
　　　　ListNode index = dummy;

　　　　//index在前面，所以判断index是否为null 就行

　　　　while(current != null && current.next!= null) {

　　　　　　//相等，将index移动向下一位
　　　　　　if(current.val == current.next.val)  {
　　　　　　　　while(current.next!= null && current.val == current.next.val) {current = current.next;}
　　　　　　　　index.next = current.next;
　　　　　　　　current = current.next;

　　　　　　}  else  {

　　　　　　　    index = current;
　　　　　　　　current = current.next;
　　　　　　　}
　　　　}
　　return dummy.next;

　　}

}

解法3：三指针法(利用三个指针和标志位flag进行处理)

public ListNode deleteDuplicates(ListNode head) {

　　ListNode pre = null;
　　ListNode current = head;

　　while (current != null) {
　　　　ListNode nex = current.next; //通过while循环始终让nex作为最快的指针，注意进行null的判断
　　　　boolean flag = false; //使用flag作为nex和cur的标志位
　　　　while (nex != null && current.val == nex.val) {
　　　　　　flag = true;
　　　　　　nex = nex.next;
　　　　}
　　　　//对重复元素进行处理
　　　　if (flag) {

　　　　　　//判断不是刚开始，进行和nex结点的连接
　　　　　　if (pre != null) { 

　　　　　　　　pre.next = nex;

　　　　　　 } else { //头部

　　　　　　　　head = nex; 

　　　　　　}

　　　　　　current = nex;
　　　　} else { //对非重复元素进行连接和跳跃
　　　　　　pre = current;
　　　　　　current = current.next;
　　　　}
　　}

　　//返回头指针
　　return head;
}

解法4：递归方法

public static ListNode deleteDuplicates(ListNode head) {
　　//baseCase
　　if (head == null || head.next == null) { return head;}

　　ListNode next = head.next;
　　//如果是这种情况
　　// 1 --> 1 --> 1 --> 2 --> 3
　　// head next
　　//1.则需要移动next直到出现与当前head.value不相等的情况（含null）
　　//2.并且此时的head已经不能要了，因为已经head是重复的节点
　　//--------------else-------------
　　// 1 --> 2 --> 3
　　// head next
　　//3.如果没有出现1的情况，则递归返回的节点就作为head的子节点
　　if (head.value == next.value) {
　　//1
　　　　while (next != null && head.value == next.value) { next = next.next; }
　　//2
　　　　head = deleteDuplicates(next);
　　} else {
　　//3
　　　　head.next = deleteDuplicates(next);
　　}
　　return head;
　　}
　　}
}

解法5：

/**

删除单链表中重复节点

原文：https://www.cnblogs.com/long2050/p/12334082.html