📌 문제풀이

🔥 문제 1

단방향 LinkedList에서 중간에 있는 노드를 삭제하시오. 단 당신은 첫번째 노드가 어디있는지 모르고 오직 삭제할 노드만 갖고 있다.

🔥 아이디어

🧿 Code

public class Problem_DeleteMiddleNode {
    public static void main(String[] args) {
        Node n = new Node(1);
        for(int i=2;i<10;i++){
            n.append(i);
        }
        solution(n.find(4));
        n.retrieve();
    }

    private static boolean solution(Node n) {
        if(n==null||n.next==null) return false;
        Node next = n.next;
        n.val=next.val;
        n.next=next.next;
        return true;
    }
}

🔥 문제 2

어떤 숫자를 자리수별로 한개씩 Linked List에 담았다. 그런데 1의 자리가 헤더에 오도록 거꾸로 담았다. 이런식의 Linked List 두 개를 받아서 합산하고 같은식으로 Linked List에 담아서 반환하라.

🧿 코드

private static Node solution(Node n1, Node n2,int carry) {
    if(n1==null && n2==null && carry==0 ) return null;

    Node result = new Node();
    int value = carry;

    if(n1!=null){
        value +=n1.val;
    }
    if (n2 != null) {
        value += n2.val;
    }
    result.val = value%10;

    if(n1!=null || n2!=null){
        Node next = solution(n1==null ? null : n1.next,
                            n2==null ? null : n2.next,
                            value>=10?1:0);
        result.next=next;
    }
    return result;
}

🔥 문제2)- Advanced Level

🔥 아이디어

• null을 만나면 stop. 뒤에 있는 결과 값을 재귀로 앞으로 전달해야 한다

• Result의 Node값과 , Carry값을 동시에 전달해야 하므로 참조전달을 사용한다.

• 자리수가 바뀌어서 Carry가 전달되는 것도 고려해야 한다.

결과값을 받아서 carry로 사용해야 한다

carry의 결과값을 받으면 정작 합계 결과를 저장하고 있는 Node는 받을 수가 없다.

그래서 객체의 값을 전달하는 것으로 사용

🧿 코드

public class GetSumOfNumber_Advanced {
    public static void main(String[] args) {
        Node n1 = new Node(9);
        n1.append(1);

        Node n2 = new Node(1);
        n2.append(1);

        Node solution = solution(n1, n2);

        while(solution.next!=null){
            System.out.println(solution.val);
            solution=solution.next;
        }
        System.out.println(solution.val);

    }
    private static Node solution(Node n1, Node n2) {
        int length1 = getListLength(n1);
        int length2 = getListLength(n2);

        if(length1>length2){
            n2 = addZeroToHead(n2,length1-length2);
        }else{
            n1 = addZeroToHead(n1,length2-length1);
        }

        Storage storage = addLists(n1,n2);

        if(storage.carry==0){
            return storage.result;
        }else{
            storage.result = insertBefore(storage.result,storage.carry);
            return storage.result;
        }
    }

    private static Storage addLists(Node n1, Node n2) {
        if(n1==null && n2==null){
            Storage storage = new Storage();
            return storage;
        }
        Storage storage = addLists(n1.next,n2.next);

        int value = storage.carry + n1.val + n2.val;
        int data = value%10;

        storage.result = insertBefore(storage.result, data);
        storage.carry = value/10;
        return storage;
    }
    private static int getListLength(Node n){
        int total=1;
        while(n.next!=null){
            n=n.next;
            total++;
        }
        return total;
    }
    // 노드 앞에 새로운 노드를 추가
    private static Node insertBefore(Node node,int data){
        Node before = new Node(data);
        if(node!=null){
            before.next=node;
        }
        return before;
    }

    private static Node addZeroToHead(Node n,int length){
        Node head = n;
        for(int i=0;i<length;i++){
            head = insertBefore(head,0);
        }
        return head;
    }

    static class Storage{
        int carry=0;
        Node result=null;
    }
}

🔥 문제3

주어진 두 개의 단방향 Linked List에서 교차되는 노드를 찾으시오.
(단, 교차점은 값이 아닌 주소로 찾아야 한다.)

아래는 문제에서 주어지는 값의 형태

🔥 아이디어

짧은 것의 길이 만큼 맞춰주고, 주소 값이 같은 것이 반환되는 것을 찾는다.

즉, 짧은 길이에 맞추어서 앞에 거를 잘라준다.

• 코드로 구현은 안함

🔥 문제4

Linked List안에 루프가 있는지 확인하고, 루프가 시작되는 노드를 찾으시오

🔥 아이디어

두 개의 포인터를 선언
(토끼와 거북이)

토끼는 거북이보다 2배 빠름

거북이가 K만큼 움직여서 시작점에 도착하면, 토끼는 loop 안에서 K만큼 움직였음

루프 안에서의 토끼 위치 R(K) = K % (루프의 길이) 가 돼야한다.

거북이가 처음 루프에 들어갔을 때 토끼와 거북이 위치의 차이는 loop length - K 만큼 차이가 난다.

그러면 언제 따라잡히냐?

속도가 2배 차이 나므로, 거북이가 L-k 만큼 움직이면 토끼는 2(L-k) 만큼 움직인다.

그러므로 거북이가 L-k만큼 움직이는 점에서 만난다.

그렇다면 잡힌 점에서, 출발점까지의 거리가 K라는 말이다.

그렇다면 K만큼 다시 거북이를 움직이게 하면 출발 노드를 찾을 수 있는 것이다.
(토끼를 움직여도 됨. 이 때 토끼는 거북이와 같은 속력으로 가야함)

• 결과적으로 첫번째는 2배의 속력으로 만난 점. 그리고 그 만난점에서 출발.
• 그 이후 1배의 속력으로 만난 점이 출발 노드인 것.

🧿 코드

public class FindLoopBeginNode {
    public static void main(String[] args) {

        Node n1 = new Node(1);
        Node n2 = n1.addNext(2);
        Node n3 = n1.addNext(3);
        Node n4 = n1.addNext(4);
        Node n5 = n1.addNext(5);
        Node n6 = n1.addNext(6);
        n6.linking(n4);

        Node solution = solution(n1);

        System.out.println(solution.val);
    }

    private static Node solution(Node head) {
        Node turtle = head;
        Node rabbit = head;

        while(rabbit!=null && rabbit.next!=null){
            turtle = turtle.next;
            rabbit = rabbit.next.next;
            if(turtle==rabbit) break;
        }
        if(rabbit==null || rabbit.next==null)
            return null;

        turtle = head;

        while(turtle!=rabbit){
            turtle=turtle.next;
            rabbit=rabbit.next;
        }
        return rabbit;
    }
}