리트코드 19일차

19. Remove Nth Node From End of List

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head.next == null && n < 2){
            return null;
        }
        ListNode ans = head;
        ListNode prev = null;

        while (head != null){
            ListNode temp = head;
            int cnt = 0;
            while (temp != null && cnt < n){
                cnt++;
                temp = temp.next;
            }

            if (temp == null && cnt == n){
                if (prev == null){
                    ans= ans.next;
                }else{
                    prev.next = head.next;
                }
            }
            prev = head;
            head = head.next;
        }
        return ans;
    }
}

풀긴했지만 코드의 가독성이 마음에 들지 않는다.

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode res = new ListNode(0, head);
        ListNode dummy = res;

        for (int i = 0; i < n; i++){
            head = head.next;
        }

        while (head != null){
            head = head.next;
            dummy = dummy.next;
        }
        dummy.next = dummy.next.next;

        return res.next;
    }
}

나와 같은 방식을 가진 코드가 답에 있었다. 엄청 깔끔하다. 방식도 정돈되어 있었는데 투 포인터로 간격만큼 미리 떨어지게 하고 null 이 나오는 순간 처리하는 방식이었다. 

이런 코드를 짜려면 생각이 잘 정돈되어야 할 것 같다.

 

라고 한다. 수학문제 같다. 많이 풀어보는 수 밖에 없어보인다.

 

82. Remove Duplicates from Sorted List II

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0) , fast = head, slow = dummy;

        slow.next =fast;
        while(fast != null){
            while(fast.next != null && fast.val == fast.next.val){
                fast = fast.next;
            }
            if (slow.next != fast){
                slow.next =fast.next;
                fast = slow.next;
            }else{
                slow = slow.next;
                fast = fast.next;
            }
        }
        return dummy.next;
    }
}

15분동안 열심히 이렇게 저렇게 찔러봤는데 못 풀어서 답을 봤다..

투포인터까지는 맞았는데 slow, fast 로 푸는지는 몰랐다. 방금전에 풀었던 것처럼 풀려고 노력했는데 사로잡혀있었나보다.

 

 

61. Rotate List

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || k < 1){
            return head;
        }
        ListNode res = head;
        ListNode fast = head; 
        ListNode slow = head;
        int size = 0;

        while ( fast != null){
            fast = fast.next;
            size++;
        }
        fast = head;

        for (int i = 0; i < k % size; i++){
            fast = fast.next;
        }
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        fast.next= res;
        res = slow.next;
        slow.next = null;

        return res;
    }
}

코드가 복잡해보인다..

풀리긴 했지만 이게 아닌 것 같다..

답안을 찾아보니 접근방법은 맞았다!

 

완료!