[Java 문제풀이] LinkedList, removeDuplicate

문제

A Node class is provided for you in the editor. A Node object has an integer data field, , and a Node instance pointer, , pointing to another node (i.e.: the next node in a list).

A removeDuplicates function is declared in your editor, which takes a pointer to the  node of a linked list as a parameter. Complete removeDuplicates so that it deletes any duplicate nodes from the list and returns the head of the updated list.

Note: The  pointer may be null, indicating that the list is empty. Be sure to reset your  pointer when performing deletions to avoid breaking the list.

122345 와 같은 순서로 LinkenList 를 input 으로 받았을때, 반복되는 숫자를 삭제하는 removeDuplicate 함수 구현하기 

Full Source Code (Including LinkedList code)

import java.io.*;
import java.util.*;
class Node{
    int data;
    Node next;
    Node(int d){
        data=d;
        next=null;
    }
    
}
class Solution
{
    public static Node removeDuplicates(Node head) {
      //문제 solution
        Node start = head;
        while(head.next !=null){
            if(head.data != head.next.data){
                head = head.next;
            }else{
                //반복되는 값이 나오지 않을때까지 loop
                while(head.data ==head.next.data){
                    if(head.next.next==null){
                        head.next=null;
                        break;
                    }else{
                    head.next = head.next.next;
                    }
                }
            }
        }
        return start;
               
    }

     public static  Node insert(Node head,int data)
     {
        Node p=new Node(data);          
        if(head==null)
            head=p;
        else if(head.next==null)
            head.next=p;
        else
        {
            Node start=head;
            while(start.next!=null)
                start=start.next;
            start.next=p;

        }
        return head;
    }
    public static void display(Node head)
        {
              Node start=head;
              while(start!=null)
              {
                  System.out.print(start.data+" ");
                  start=start.next;
              }
        }
        public static void main(String args[])
        {
              Scanner sc=new Scanner(System.in);
              Node head=null;
              int T=sc.nextInt();
              while(T-->0){
                  int ele=sc.nextInt();
                  head=insert(head,ele);
              }
              head=removeDuplicates(head);
              display(head);

       }
    }

다른사람의 문제풀이 - Recursive 로 문제해결 

public static Node removeDuplicates(Node head) {
    if (head == null || head.next == null){
        return head;
    }
    if (head.data == head.next.data){
        head.next = head.next.next;
        removeDuplicates(head);
    }else{
        removeDuplicates(head.next);
    }
    return head;
}

head.next 가 null 인 경우를 base 로 잡고 recursive 로 문제를 해결했다. 

Recursive 로 문제를 해결할 수 있는 조건 

1) 재귀의 호출은 같은 문제 내에서 더 범위가 작은 값, 즉, 하위 문제에 대해 이루어져야 한다.

2) 재귀함수 호출은 더 이상 반복되지 않는 base case에 도달해야 한다.

출처 https://www.hackerrank.com/challenges/30-linked-list-deletion/problem