Today I Learned

오늘 할일
1. LeetCode
2. 영상처리 과제
3. 창엔 2일차
4. 리팩토링 마틴 파울러?
5. 카드 발급

오늘 한일
1. LeetCode

• 328. Odd Even Linked List을 최대한 LeetCode 내에서 해결하려 했으니

/**
 * 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 oddEvenList(ListNode head) {
        /*
            시간복잡도 O(n), 공간복잡도 O(1)로 홀수번째 node를 뒤로 link
         */
        //1. 예외처리(head가 비어있거나 하나일 경우)
        if(head==null){
            return null;
        } else if(head.next==null){
            return head;
        }

        //2. 전체 size 계산
        int size=1;
        for(ListNode i=head; i.next!=null; i=i.next){
            size++;
        }
        System.out.println("size: "+size);

        ListNode head2=null, iter2=null, iter=head, prev=head;
        for(int i=0; i<size; i++){
            System.out.printf("loop_%d) prev: %d, iter: %d / ", i, prev.val, iter.val);
            if(i%2==0){//인덱스 짝수는 iterator를 ++하여 넘어감
                prev=iter;
                iter=iter.next;
                System.out.printf("After, prev: %d, iter: %d\n", prev.val, iter.val);
                continue;
            } else if (iter==null){//이 경우는 현재 로직상 오류임
                System.out.println("ERROR");
                break;
            } else{//인덱스 홀수
                //우선 지울 원소를 head2에 추가
                if(head2==null){//만약 처음으로 추가하는 거라면 head2 초기화
                    head2=iter;//
                    head2.next=null;
                    iter2=head2;
                } else{
                    iter2.next=iter;//다음원소 추가
                    iter2=iter2.next;//다음원소로 이동
                    iter2.next=null;//다다음 원소 null로 초기화
                }
                System.out.println("maybe");
                //원소삭제
                iter=iter.next;
                prev.next=iter;
                prev=prev;
                System.out.println("maybe");
            }//endelse
        }//endfor

        //head1끝에 head2붙이기
        prev.next=head2;

        return head;
    }
}

코드 내에서 원소 삭제 후 prev.val과 iter.val에 접근이 안되는 점을 발견했지만 어느 부분에서 문제가 발생되는지 디버깅 없이 찾아내기 어렵다고 판단하였다.

디버깅 결과 head2=iter같은 부분에서 얕은 복사가 이루어 지고있는 것을 확인했다.

	private ListNode copyObject(ListNode node){
        ListNode result=new ListNode();
        ListNode iter=result;

        while(node.next!=null){
            iter.val=node.val;
            iter.next=new ListNode(node.next.val);
            iter=iter.next;
            node=node.next;
        }

        return result;
    }

아래와 같이 새로운 객체를 만들어서 복사해야할 듯 하다. 하지만 위와 같은 함수를 사용하기보다는 next에 객체를 연결할 경우 필요한 경우에만 만들게끔 하였다.

public ListNode oddEvenList(ListNode head) {
        /*
            시간복잡도 O(n), 공간복잡도 O(1)로 홀수번째 node를 뒤로 link
         */
        //1. 예외처리(head가 비어있거나 하나일 경우)
        if(head==null){
            return null;
        } else if(head.next==null){
            return head;
        }

        //2. 전체 size 계산
        int size=1;
        for(ListNode i=head; i.next!=null; i=i.next){
            size++;
        }

        ListNode head2=null, iter2=null, iter=head, prev=head;
        for(int i=0; i<size; i++){
            if(i==0){
                iter=iter.next;
            } else if(i==1){
                head2=new ListNode(iter.val);
                iter2=head2;
                iter=iter.next;
                prev.next=iter;
            } else if(i==size-1){//merge
                iter.next=head2;
            } else if(i%2==0){
                prev=iter;
                iter=iter.next;
            } else if(i%2==1){
                iter2.next=new ListNode(iter.val);
                iter2=iter.next;
                iter=iter.next;
                prev.next=iter;
            }//공통코드는 없다.
        }//endfor

        return head;
    }

드디어 실행이 되기는 했다!