编程题：删除链表中的重复结点

心已赠人 2022-05-21 11:54 143阅读 0赞

## 题目描述 ##

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

### 思路： ###

可以定义一个first对象（值为-1，主要用于返回操作后的链表），first.next指向head，定义一个last同样指向first（主要用于操作记录要删除节点的前一个节点），定义一个p指向head，指向当前节点。

操作流程：

①先判断当前p指向与p.next指向是否为空，为空则进入⑤，不为空进入②；

②判断当前节点p的值与与p.next的值是否相等，如果相等，进入③，不相等，进入④

③记录p.val的值为val，循环判断val是否与当前p指向相等，相等的话p = p.next，last.next指向p；

④last指向p，p指向p.next；

⑤返回first.next；

### 代码： ###

package com.example.shirodemo;
    
    import java.util.*;
    
    /**
     * Created by ASUS on 2018/7/2
     *
     * @Authod Grey Wolf
     */
    public class Practice {
        private  static ListNode head=null;
        private  static  ListNode temp=null;
    
        public static void main(String[] args) {
            Practice practice = new Practice();
            practice.sys();
        }
    
        private void sys() {
            Scanner scan=new Scanner(System.in);
            System.out.println("输入结点数:");
            int n=scan.nextInt();
            int i;
           for (i=0;i<n;i++){
                addNode(scan.nextInt());
            }
            System.out.println("输出最初的单链表：");
            printNode(head);
            System.out.println();
            ListNode listNode1=deleteDuplication(head);
            System.out.println("输出处理后的单链表");
            printNode(listNode1);
        }
    
        /**
         * 增加结点
         * @param val
         */
        private void addNode(int val){
            ListNode listNode=new ListNode(val);
            if (head==null){
                head=listNode;
                return;
            }
            temp=head;
            while (temp.next!=null){
                temp=temp.next;
            }
            temp.next=listNode;
    
        }
    
        /**
         * 输出单链表
         * @param listNode
         */
        private void printNode(ListNode listNode){
            if (listNode==null){
                System.out.println("该链表为空");
                return;
            }
            while (listNode.next!=null){
                System.out.print(listNode.val+"-->");
                listNode=listNode.next;
            }
            System.out.println(listNode.val);
        }
    
        /**
         * 删除重复结点
         * @param pHead
         * @return
         */
        private ListNode deleteDuplication(ListNode pHead) {
            ListNode first=new ListNode(-1);
            first.next=pHead;
            ListNode last=first;
            ListNode p=pHead;
    
            while (p!=null&&p.next!=null){
                if (p.val==p.next.val){
                    int val=p.val;
                    while (p!=null&&p.val==val){
                        p=p.next;
                        last.next=p;
                    }
                }else {
                    last=p;
                    p=p.next;
                }
            }
            return first.next;
        }
    
    
    }
    
    class ListNode{
        int val;
        ListNode next=null;
    
        ListNode(int val){
            this.val=val;
        }
    }

### 效果：    ###

输入结点数:  
7  
1 2 3 3 4 4 5  
输出最初的单链表：  
1-->2-->3-->3-->4-->4-->5  
  
输出处理后的单链表  
1-->2-->5

我的座右铭：不会，我可以学；落后，我可以追赶；跌倒，我可以站起来；我一定行。