[해커랭크] Delete duplicate-value nodes from a sorted linked list

문제링크: www.hackerrank.com/challenges/delete-duplicate-value-nodes-from-a-sorted-linked-list/problem

Delete duplicate-value nodes from a sorted linked list | HackerRank

아주 재밌는 문제였다.

두 가지 방법으로 풀었다. 비슷한 방식이지만 처음 문제를 풀고나니 재귀로 간결하게 풀릴 것 같아서 바로 다시 풀었다.

 

방법1 

-포인터cur와, nNode가 있다. nNode의 데이터가 cur의 데이터와 다를 때까지 이동하고 cur의 next를 nNode로 한다.

그리고 cur를 nNode의 위치로 이동한다. 이것을 반복한다.

 

방법2

-재귀를 이용한다. 현재 Node의 next가 같을 경우 next의 next를 가리키도록 한다. 이 때 next의 next는 같지 않은 숫자를 가리킨다고 판단한다. next가 재귀 호출돼서 먼저 자신과 다른 숫자를 가리키고 있을 것이기 때문이다.

 

 

방법1코드

static SinglyLinkedListNode removeDuplicates(SinglyLinkedListNode head) {
        SinglyLinkedListNode cur = head;
        SinglyLinkedListNode nNode = head;
        while(true){
            if(nNode==null) {
                cur.next = null;
                break;
            }
            if(cur.data == nNode.data){
                nNode = nNode.next;
            }else{
                cur.next = nNode;
                cur= cur.next;
            }
        }
        return head;
    }

 

방법2코드

static SinglyLinkedListNode removeDuplicates(SinglyLinkedListNode head) {
        if(head.next==null) return head;
        head.next = removeDuplicates(head.next);
        if(head.data == head.next.data){
            head.next = head.next.next;
        }
        return head;
    }