7주차. 연결리스트 복습(두 정렬 리스트의 병합)

https://memodayoungee.tistory.com/39

5주차. 연결 리스트(두 정렬 리스트의 병합)

복습했던 문제.

 

때는 바야흐로 12일. 팀원 모두가 "연결 리스트" 라는 난관에 봉착했다. 백준 문제는 돌아가며 풀이했지만, 아무도 속 시원하게 연결리스트 문제에 대해서 얘기하지 못했다. 

 

아무것도 모른 채 답만 보며 문제를 낭비할 바에 복습을 하자는 의견이 나와 6주차는 백준문제 2문제와 우리가 풀었던 연결리스트 문제를 복습하기로 했다. 그리고 난 손코딩으로 하나하나 따라가며 디버깅해 본 결과 큰 깨달음을 얻게되는데...

 

※ 배열로 변환하거나 리스트로 변환해서 간단하게 풀이할 수 있겠지만, 주제가 연결리스트니 연결리스트를 직접 조작하여 문제를 풀어보고 의논해보는 것이 스터디의 의미가 아닐까.. 싶었다.

※ 재귀함수에 약한 나

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1!=null && list2!=null)
        {
            if(list1.val < list2.val)
            {
                list1.next =  mergeTwoLists(list1.next,list2);
                return list1;
            }
            else
            {
                list2.next = mergeTwoLists(list1,list2.next);
                return list2;
            }
        }
        if(list1 == null)
            return list2;
        return list1;
    }

설명을 잘 못하는 0개국어 한국인이지만, 최대한 쉽게 풀어보겠다.

 

list1.next =  mergeTwoLists(list1.next,list2);
list2.next = mergeTwoLists(list1,list2.next);

더 작은 값을 next로 넘겨주고 next로 반환 받는 이유: 쉽게 생각해서 제일 작은 수를 뺀 나머지 값을 전부 인자값으로 넘기고, 반환된 값을 그 제일 작은 값 next로 이어준다고 생각했다. (조건문을 보면 제일 작은 수 기준으로 그 앞에 연결된 next노드를 넘겨줌)

 

나머지 팰린드롬 연결리스트, 역순 연결리스트는 스터디시간에 설명했으니까 패쓰~