Linked List | Middle of the Linked List

Given a non-empty, singly linked list with head node head, return a middle node of linked list. If there are two middle nodes, return the second middle node.

LinkedList에서 가운데에 있는 Node를 리턴하라는 문제이다. 처음 접근은 1.5N의 loop을 돌리는 방식이었다. 

class Solution {
    public ListNode middleNode(ListNode head) {
        int count = 0;
        ListNode curr = head;
        while(curr != null){
            curr = curr.next;
            count++;
        }
        
        curr = head;
        count = count/2;
        while(count > 0){

            curr = curr.next;
            count--;
        }
        return curr;
    }
}

* Time Complexity: O(N), 실제로는 1.5N이다.

* Space Complexity: O(1), 카운트, 그리고 curr라는 노드 포인터만 사용했다.

 

노드 갯수를 세어서, 그 갯수를 2로 나눠준만큼 다시 head부터 이동하면, 가운데 노드가 된다. 문제의 조건에서 '가운데'를 명확하게 해주었다. 홀수일때는 당연히 정가운데 있지만, 짝수일때는 중간기점에서 오른쪽에있는 노드를 가운데로 칭했다. 그러면 5개라면 5/2, 즉 2번 이동한 노드, 6개 짝수 노드라면 6/2, 즉 3번 이동한 노드가 된다. 두 케이스 모두 나누기2를 해주면 계산이 되기 때문에 따로 계산할 필요는 없다. 이 해법은 3분 30초정도 걸렸다.

 

 

그이후, 또다른 신박한 해법이 떠올랐다. 바로 한번의 Loop만에 해결할 수 있는 방법이다.

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

* Time Complexity: O(N)

* Space Complexity: O(1), slow 그리고 fast 노드 포인터를 사용했다.

 

slow와 fast노드 포인터를 만들어서, slow는 한노드씩, fast는 두 노드씩 이동하면 된다. 그러면 fast가 NULL이거나(노드 총 갯수가 짝수일경우), fast의 다음 노드가 NULL이면(노드 총 갯수가 홀수일 경우) slow는 자동으로 중간지점에 있게 된다. 코드도 훨씬 간결하고 O(N)으로 해결할 수 있다. 테스트 결과 제일 빠른 속도가 나왔고, 메모리는 많이 사용하는것으로 나왔다. 아마 포인터를 두개 사용하기 때문일 것이다. 이 해법은 2분남짓 걸렸다.

2번째 해법이 더 좋았지만, 문제에서 준 조건은 노드의 총 갯수가 1-100개였기 때문에, 결국 O(N)이 아닌 O(1)이기 때문에 (Max 100), 1.5번 돈다고 해도 O(150)으로 역시 Constant이다. 이런 경우에는 1.5N이더라도 메모리를 더 적게 사용하는게 효율적이라는 생각이다. 그래서 두번째 해법이 더 많은 노드 갯수 리밋이 있을때는 효율적이겠지만, 이 문제의 조건에서는 (Max 100개), 첫번째 방식이 더 효율적이다.

 

가장 가운데 포켓몬을 찾으려면? 총 몇마리인지 모른다면!! 이상해씨부터 시작해서 한손가락은 두칸씩, 다른한손가락은 한칸씩 움직여서, 많이 움직이는 손가락이 뮤에 닿았거나 뮤 다음 빈칸이라면! 그것이 바로 가운데 포켓몬이다. 정답은 바로 데구리! 꼬마돌이 진화한 형태로 두번째 진화를 하게되면 제모오옥은 딱구리 돌몸을 곁들인...

 

 

 

Reference

leetcode.com/problems/middle-of-the-linked-list/

Middle of the Linked List - LeetCode

 

The Definitive Ranking of the Original 151 Pokemon