.leetcode(21. Merge Two Sorted Lists)

https://leetcode.com/problems/merge-two-sorted-lists/

 

3. 2022/05/06 시도

소요시간: 4분

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode current = new ListNode();
        ListNode head = current;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                current.next = list1;
                list1 = list1.next;
            } else {
                current.next = list2;
                list2 = list2.next;
            }
            current = current.next;
        }
        
        current.next = list1 == null ? list2 : list1;
        
        return head.next;
    }
}

풀이 접근 과정

나중에 리스트를 리턴할 때, head부분을 리턴해야되기때문에 더미노드(current)를 만들어준다.
그리고 그걸 head에 넣어둔다. 이러면 나중에 head.next만 하면 리턴값을 제대로 보내줄 수 있다.

그리고 두 노드를 비교하면서 연결해준다.

마지막에 null여부에 따라 만들어준 current 노드 뒤에 이어준다.

 

느낀점

• 기존에 풀었던 문제라서 쉽게 풀렸다.

---

2. 2022.01.24 시도

소요시간: 10분(구상 2분, 코딩 8분)

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }

        if (list2 == null) {
            return list1;
        }
        
        ListNode p1 = list1;
        ListNode p2 = list2;
        ListNode head = new ListNode();
        
        ListNode prev = head;
        while(p1 != null && p2 != null) {
            if (p1.val < p2.val) {
                ListNode target = p1;
                p1 = p1.next;
                prev.next = target;
                prev = target;
            } else {
                ListNode target = p2;
                p2 = p2.next;
                prev.next = target;
                prev = target;
            }
        }
        if (p1 == null) {
            prev.next = p2;
        } else if (p2 == null) {
            prev.next = p1;
        }
        
        return head.next;
    }
}

풀이 접근 과정

리턴해주기 위해서 헤드노드 변수를 할당해준다.

일단 각 파라미터에 대한 null처리하고 포인터 두개를 잡고 비교하고 그 다음에 붙여주고 하면 되겠다. 그때 .next에 연결해주어야하기때문에 prev라는 변수를 두어 앞의 노드를 기록해 둔다.

while문이 끝난 뒤에 남은 노드들이 있을 수 있므로 각 경우에 따라 남은 노드를 붙여준다.

 

느낀점

• 예전에 풀었던 잔상이 머리에 남아있었던 것 같다. 풀이가 하나둘씩 생각나서 풀어낼 수 있었다.
• 풀이를 보니 recursion도 가능하다 싶어서 한번 풀어보았다. 원리는 간단하다. 마지막부터 정해주면 되는 것이다.

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }

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

 

---

 

1. 2021.01.04 시도

소요시간: 34분

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else  if (l2 == null) {
            return l1;
        }

        ListNode ret = new ListNode();
        ListNode start = ret;

        while (l1!=null && l2!=null) {   
            if (l1.val == l2.val) {
                ret.next = new ListNode(l1.val);
                ret.next.next = new ListNode(l1.val);
                ret = ret.next.next;
                l2 = l2.next;
                l1 = l1.next;
            } else if (l1.val > l2.val) {
                ret.next = new ListNode(l2.val);
                ret = ret.next;
                l2 = l2.next;
            } else if (l1.val < l2.val) {
                ret.next = new ListNode(l1.val);
                ret = ret.next;
                l1 = l1.next;
            }
        }

        while(l1 != null) {
            ret.next = new ListNode(l1.val);
            ret = ret.next;
            l1 = l1.next;
        }

        while(l2 != null) {
            ret.next = new ListNode(l2.val);
            ret = ret.next;
            l2 = l2.next;
        }

        return start.next;
    }
}

풀이 접근 과정

한번씩 읽으면 되기때문에 O(m+n)정도 걸릴것이다.

제한조건이 꽤나 타이트한데 무슨 이유때문일까?

리쿼젼으로 맨뒤부터 생각하면 될거같다. 근데 생각해보니 list길이가 다르면 처리가 좀 복잡해질 수도 있겠다.
for/while문으로 하나씩 채워가는게 더 쉬울거같다.

 

느낀점

• 생각보다 오래걸리고 복잡했다. ret.next를 헷갈려 덮어씌워서 데이터가 잘못 나오기도 했다.
• iterative하게 풀었는데 공간도 많이 사용하고 개념적으로 복잡하게 했다.
• 솔루션들은 매우 간단했다. 리스트노드의 특성을 십분 활용했던점이 내가 배워야할 점이었다.
• 그래도 iteration방법에서 시작점을 잡는거나 마지막에 이어주는걸 코드로 구현했다는 점에서 다행이었다.

#recursion을 이용한 풀이: 작은것 뒤에 붙이는게 포인트
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else  if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }   
    }
}

#iteration을 이용한 풀이: 포인트는 시작점을 잡아두는 것과 마지막에 이어주는 것
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode ret = new ListNode();
        ListNode start =ret;
        while(l1!=null && l2!=null) {
            if (l1.val < l2.val) {
                ret.next = new ListNode(l1.val);
                l1 = l1.next;
            } else {
                ret.next = new ListNode(l2.val);
                l2 = l2.next;
            }
            ret = ret.next;
        }

        ret.next = l1==null ? l2 : l1;

        return start.next;
    }
}

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형