연결리스트

 

1. 팰린드롬 연결 리스트 

 

1. 내풀이(13ms) 스택 이용한 풀이

 public boolean isPalindrome(ListNode head) {
        ListNode cur = head;
        Stack<Integer> st = new Stack<>();
        st.push(cur.val);
        while(cur.next != null){
            cur = cur.next;
            st.push(cur.val);
        }
        while(!st.isEmpty()){
            int stVal = st.pop();
            if(stVal != head.val){
                return false;
            }
            head = head.next;
        }
        return true;
    }

 

 

2. 데크를 이용한 풀이 (12ms)

 public boolean isPalindrome(ListNode head) {
        
        Deque<Integer> deque = new LinkedList<>();
        while(head != null){
            deque.add(head.val);
            head = head.next;
        }

        while(!deque.isEmpty() && deque.size() > 1){
            if(deque.pollFirst() != deque.pollLast()){
                return false;
            }
        }

        return true;
    }

 

3. 러너를 이용한 풀이 (3ms)

public boolean isPalindrome(ListNode head) {
        
        ListNode fast = head, slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //홀수 개 느린 러나가 한 칸 더 앞으로 가도록 처리 
        if(fast != null){
            slow = slow.next;
        }

        //중간에 도달한 느린러너 기준으로 역순 연결리스트 만들기 
        ListNode rev = null;
        while(slow != null){
            ListNode next = slow.next;
            slow.next =rev;
            rev = slow;
            slow = next;
        }

        while(rev != null){
            if(rev.val != head.val)
            return false;

            rev= rev.next;
            head = head.next;
        }

        return true;
    }

 

-> 그림그려서 나중에 해보자..

 

* 러너 기법

 

연결 리스트 순회시 2개의 포인터 동시에 사용하는 기법, 한 포인터가 다른 포인터보다 앞서게 하여 병합지점 혹은 중간 위치, 길이 등을 판별할 때 유용하다! 

- 빠른러너너 2칸씩 느린러너 한칸씩 빠른러너가 끝에 닿으면, 느린러너는 중간에 가있다. 

- 중간 값을 찾을 때 편하게 이용할 수 있다 (연결리스트에서 자주 사용한다!)

 

* 데크 자료형 

 

- 구현 LinkedList, ArrayDeque 자료형이 구현체이다 

- LinkedList는 내부 구현이 연결리스트, ArrayDeque는 배열이다. 

- LinkedList는 List의 구현체이기도 하다. 

 

* 연결리스트 시간복잡도 

 

- 탐색 (N) 양끝 조회,삽입 (1)

 

- 두 정렬 리스트 병합 (리트코드 21)

 

내 풀이 (0ms)

 public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode result = new ListNode();
        ListNode head = result;
        //일단 next부터 가야함 result.next에 list1, list2 넣음 -> 둘이 비교해서 작은거 넣고 다음에 next
        //다 돌고 나온 다음에 마지막에 한번에 넣어주는 작업 아니면 그냥 재귀에서 처리
        
        if(list1==null && list2 == null){
            return null;
        }

        merging(result, list1, list2);

         if(result != null){
            ListNode cur = result;
            ListNode pre = cur;
            while(cur.next != null){
                pre = cur;
                cur = cur.next;
            }
            pre.next = null;
        }


        return result;
    }

    public static void merging(ListNode result, ListNode t1, ListNode t2) {

        if(t1 == null && t2 == null){
            return;
        }else{
            //nextnode;
            //if(t1.next != null || t2.next != null)
             result.next = new ListNode();
            //t1만 null인 경우
            if(t1 == null){
                result.val = t2.val;
                merging(result.next, t1, t2.next);
            //t2만 null인 경우
            } else if (t2 ==null) {
                result.val = t1.val;
                merging(result.next, t1.next, t2);
            }else{
                //둘다 null이 아닌 경우 (값 비교)
                if (t1.val < t2.val) {
                    result.val = t1.val;
                    merging(result.next, t1.next, t2);
                } else {
                    result.val = t2.val;
                    merging(result.next, t1, t2.next);
                }
            }
        }
    }

 

 

- 재귀 구조로 연결 

//list1 (1,2), list2 (3,4) -> 1->2->3->4  
//(애초에 병합이 list값 두개 비교해서 작은 것에 그 다음은 작은 것 다음과 기존 거 비교 연결하고 작은 것 리턴)  
//재귀란 선언형이다!!
public ListNode mergeTwoLists(ListNode list1, ListNode list2){

	if(list1 == null) return list2;
    if(list2 == null) return list1;
    
    if(list1.val < list2.val){
    	list.next = (mergeTwoLists(list1.next,list2); //선언형 list.next연결  
        return list1; //list1이 더 작으니 둘 중 더 작은 것 리턴
    }else{
    	list2.next = mergeTwoLists(list1,list2.next);
        return list2;
    }
}

 

 

- 역순 연결리스트 (206)

 

> 재귀 구조로 뒤집기 

//(1,2,3) 
public ListNode reverse(ListNode node, ListNode prev){

	if(node == null)
    	return prev;
	//현재 노드의 다음 노드를 미리 지정
    ListNode next = node.next;
    //현재 노드의 다음으로 이전 노드 지정 
    node.next = prev;
    return reverse(next,node); // 꼬리 재귀 
}

public ListNode reverseList(ListNode node){
	return reverse(head,null);
}

// 1 null -> (2,1) -> (3,2)
// next = 2; -> next =3     -> next =null
// 1.next=null -> 2.next = 1 -> 3.next = 2 -> 3리턴

// 약간 재귀를 통해 버블 정렬 처럼 이전 값 넘기면서 전환 

//반복구조로 풀기 
ListNode next = head;
ListNode pre = null;
while(node != null){
	
    next = node.next;
    node.next =pre;
    
    pre =node;
    node = next;
    
}

 

 

 

* 재귀 문제 리턴 값 생각하기 

-> 꼬리재귀 --> 종료조건에 리턴값이 전체 리턴 값 

-> 나머지 재귀 -> 첫 재귀호출시 리턴값이 전체 리턴값 

-> 재귀 호출은 항상 이동이 생기는 부분에 걸도록 하자! 

-> 논리적으로 식을 생각할때 n을 사용해서 생각해보자.. n과 n-1..느낌으로 

-> 가장 쉬운 예시로 재귀식을 생각해보도록 한다! 재귀는 선언형 코드이다!  (마치 sql!)

 

 

 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
         //2 4 3 + 5 6 4 = 7 0 8
       
        Stack<Integer> st = new Stack<>();
        List<Integer> ar = new ArrayList<>();
        ListNode re = new ListNode();
        //근데 그냥 더하고, 다시 for문으로 10넘어가면 옆으로 넘기면..안대나?
        //스택에다가 넣어두고
        //3개 같이 더하기 아 3자리는 불가군 오케 그렇게 가보자
        if(l1 == null && l2 == null){
            return null;
        }
		
        //일단 모두 더해서 ArrayList에 담기 
        while(l1 != null || l2 != null){
            if(l1 != null && l2 != null){
                ar.add(l1.val+l2.val);
                l1 = l1.next;
                l2 = l2.next;
            }else if(l1 == null){
                ar.add(l2.val);
                l2 = l2.next;
            }else{
                ar.add(l1.val);
                l1 = l1.next;
            }
        }
        int cnt = 0;
        ListNode head = re;

        //변환은 완료 stack에 값이 empty가 아니거나, 카운터가 전체 리스트의 사이즈보다 작다면
        //반복문 계속 돌아라!
        while(!st.isEmpty() || cnt < ar.size()){

            ListNode newnode = new ListNode();
            int num = 0;

            if(cnt < ar.size()) { //cnt가 전체 리스트의 사이즈보다 작다면 일단 값을 꺼내옴
                num += ar.get(cnt);
            }

            if(!st.isEmpty()){ //스택에 값이 있다면 값을 꺼내옴
                num += st.pop();
            }
            newnode.val  = num %10; //노드에는 10의 나머지만 저장
            re.next = newnode;
            re = newnode;
            cnt++;
            if(num >=10){ //num이 10보다 컸다면, 스택에 몫 저장
                st.push(num/10);
            }

        }
        return head.next; //처음에 더미 head가 만들어지기 때문에 next부터 의미 있다.
    }

 

 

1. 전자기식 구현 

 

-논리 회로의 전가산기와 유사한 형태로 구현해보자

- 이진법이 아닌 십진법이란 차이만 있을 뿐 자리올림수를 구하는 것 까지 가산기의 원리와 거의 동일함

- 입력값 A,B 이전의 자리올림수 3가지 입력으로 합과 자리 올림수 결정한다.

- 덧셈결과는 나머지를 취하고, 몫은 자리 올림수 형태로 올리는 구조

//값을 계산할 임시 노드 선언 
ListNode node = new ListNode(0);
//임시 노드를 첫 노드로 선언 
ListNode root = node;


//자릿수의 합, 자리올림수, 나머지를 저장할 변수 선언 
int sum, carry=0, remainder;

//모든 연결 리스트를 끝까지 순회하고, 자리 올림수도 0이 될 때까지 진행

while(l1 != null l2 != null || carry !=0){

	sum = 0;
    
    if(l1 != null){
    	sum += l1.val;
        l1 = l1.next;
    }
    
    if(l2 != null){
    	sum += l2.val;
        l2 = l2.next;
    }
    
    remainder = (sum+carry) %10; // 무조건 나머지만..
    carry = (sum+carry) /10; //아 어차피 carry가 없으면 /10해도 의미 없을 터
    
    node.next = new ListNode(remainder);
    
    node = node.next;
}

return root.next;