数据结构与算法-剑指Offer系列（17）删除链表的重复节点-Java实现

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了数据结构与算法-剑指Offer系列（17）删除链表的重复节点-Java实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3201字，纯文字阅读大概需要5分钟。

内容图文

题目17：删除链表中的重复的节点

题目描述：

在一个排序的链表中，如何删除重复的节点？

解题思路：

• 第一步确定是删除函数的参数，这个函数需要输入待删除链表的头节点，头结点可能与后面的节点重复，也就是说头结点也可能被删除，因此删除函数声明DeleteDuplicatedNode(ListNode pHead)
• 接下来遍历整个链表，如果当前节点（pNode）的值与下一个节点值相同，那么它就是重复的节点，为了保证删除后的到代码连续，要把当前节点的前一个节点（pPreNode）和后面值比当前节点的值大的节点相连，确保pPreNode始终与下一个没有重复的节点连接在一起。

代码实现：

package swordToOffer;

import swordToOffer.Num17_DeleteListNode.ListNode;

public class Num18_DeleteDuplication {

	static class ListNode{
		int val;
		ListNode next;
		public ListNode(int value,ListNode nextNode) {
			val = value;
			next = nextNode;
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//重读节点位于头部
		ListNode p4=new ListNode(3, null);
        ListNode p3=new ListNode(2, p4);
        ListNode p2=new ListNode(1, p3);
        ListNode p1=new ListNode(1, p2);
        //头结点重复
        showListNode(p1);
        //尾结点重复
        p4=new ListNode(3,null);
        p3=new ListNode(3, p4);
        p2=new ListNode(2, p3);
        p1=new ListNode(1, p2);
        showListNode(p1);
        //重复节点位于中部
        p4=new ListNode(3,null);
        p3=new ListNode(2, p4);
        p2=new ListNode(2, p3);
        p1=new ListNode(1, p2);
        showListNode(p1);
        
        //连续出现重复节点
        ListNode p6 = new ListNode(5,null);
        ListNode p5 = new ListNode(5,p6);
        p4=new ListNode(3,p5);
        p3=new ListNode(3, p4);
        p2=new ListNode(1, p3);
        p1=new ListNode(1, p2);
        showListNode(p1);
        
        //重复多个
        p6 = new ListNode(5,null);
        p5 = new ListNode(3,p6);
        p4=new ListNode(3,p5);
        p3=new ListNode(3, p4);
        p2=new ListNode(1, p3);
        p1=new ListNode(1, p2);
        showListNode(p1);
        
        //无重复
        p6 = new ListNode(6,null);
        p5 = new ListNode(5,p6);
        p4=new ListNode(4,p5);
        p3=new ListNode(3, p4);
        p2=new ListNode(2, p3);
        p1=new ListNode(1, p2);
        showListNode(p1);
        
        //null node
        ListNode p7 = null;
        showListNode(p7);
	}
	
	public static ListNode deleteDuplicatiion(ListNode pHead) {
		if(pHead==null||pHead.next==null) {  //空节点或者只有一个
			return pHead;
		}
		ListNode preNode = null;
		ListNode curNode = pHead;
		
		while(curNode!=null) {
			boolean needDelete = false;
			if(curNode.next!=null&&curNode.val==curNode.next.val) {
				needDelete = true;
				//print
			    System.out.print("The node to be deleted is: ");
			    if(curNode!=null)
			        System.out.println(curNode.val);
			    else
			        System.out.println();
			}
			if(!needDelete) {   //不是重复节点 查找下一个
				preNode = curNode;
				curNode = curNode.next;
			}else {
				int dupValue = curNode.val;
				ListNode toDeleted = curNode;
				while(toDeleted!=null&&toDeleted.val==dupValue) {
					//找下一个不重复节点
					toDeleted = toDeleted.next;
				}
				if(preNode==null) {
					pHead = toDeleted;
				}else {
					preNode.next = toDeleted;
				}
				
				curNode = toDeleted;  //节点如果重复出现 不能用next
			}
		}
		return pHead;
	}
	
	
	//	17题的显示函数
	public static void showListNode(ListNode head) {
	System.out.println("============");
    System.out.print("The original list is: ");
    ListNode curr=head;
    if(curr!=null) {
        while(curr.next!=null) {
            System.out.print(curr.val+",");
            curr=curr.next;
        }
        System.out.println(curr.val);
    }else {
        System.out.println();
    }
     
     
    curr=deleteDuplicatiion(head);    
    System.out.print("The result list is: ");
    if(curr!=null) {
        while(curr.next!=null) {
            System.out.print(curr.val+",");
            curr=curr.next;
        }
        System.out.println(curr.val);
    }else {
        System.out.println();
    }
    System.out.println("============");
}

}

 

内容总结

以上是互联网集市为您收集整理的数据结构与算法-剑指Offer系列（17）删除链表的重复节点-Java实现全部内容，希望文章能够帮你解决数据结构与算法-剑指Offer系列（17）删除链表的重复节点-Java实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---