Leetcode[day8] - 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.

Note:
The number of nodes in the given list will be between 1 and 100.

Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3. (The judge's serialization of this node is [3,4,5]).
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

1. 알고리즘을 해결하기 위해서 생각한 방법

 

 - 우선, ListNode는 next를 통해서 다음 노드로 이동할 수 있다.

 - output은 절반의 지점부터 마지막 지점까지의 부분 배열이 필요하다.

 - 절반의 지점을 알기 위해서는 head를 한 번 탐색해서, 사이즈를 알아내야 한다.

 - 사이즈를 알아낸 후, ListNode는 마지막 지점에 가 있을 것이다.

 - 다시 head로 돌아와서, count를 해주면서 절반 지점인 지점까지 이동한다.

 - 절반 지점의 ListNode는 이전 노드의 정보를 알지 못 한다.

 - ListNode answerNode = 절반 노드, 연결만 시켜주면 정답이다.

 

2. 알고리즘 작성 중, 어려운 점

 

 - 문제를 어떻게 풀 지에 대한, 생각을 이해하고 있다.

 - 하지만, ListNode를 통해서 작성한 코드가 지저분하고, 가독성이 없었다.

 - 1차적으로 작성한 코드는 정답이었지만, 리팩토링을 진행하려 한다.

 

3. 내가 작성한 알고리즘

 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        int count = 0; //ListNode의 사이즈를 카운팅하는 변수
        int pointOfMiddle = 0; //최종적으로, 중간 값으로 사용하는 변수
        ListNode currentNode = head;//다음의 다음 노드로 이동하기 위해서 사용하는 변수
        ListNode nodeOfMiddle = null;//result 변수
        while(true){//무한 반복을 하는데
            if(currentNode == null){//현재 노드가 없을 때까지, 즉, next 노드가 없다면
                break;
            }
            count++;//사이즈를 구하기 위해서 카운팅
            currentNode = currentNode.next;//currentNode에 다음 노드를 누적
        }        
        pointOfMiddle = count / 2;//중간 값
        currentNode = head;//다시 원점으로 와서
        count = 0;//다시 노드를 카운팅 해야함.
        while(true){
            if(currentNode == null){//currentNode가 없다면
                break;
            }
            if(count == pointOfMiddle){//중간 이라면, 종료하고 해당 Node를 return
                nodeOfMiddle = currentNode;
                break;
            }
            count++;
            currentNode = currentNode.next;
        }
        return nodeOfMiddle;
    }
}

4. 내가 작성한 알고리즘 결과

결과를 비교하고 싶다..

5. 내 알고리즘 리팩토링 하기

 

 - 리팩토링을 할 수 있는 부분

 (생각) 처음에 노드를 탐색한 후, 나온 정보들을 가지고, 정답을 구할 수 있을 것이라고 생각했음.

 (생각) Node는 해당 인덱스로 접근하기 위해서 n의 복잡도를 갖고 있음.

 (생각) Node는 해당 Node의 객체에 다음 객체들의 모든 정보가 담겨져 있음.

 

 - 리팩토링을 진행한 부분 

1. 굳이 중간 번호와 중간 노드에 대한 결과를 얻기 위해서 변수로 만들지 않고, head에서 처리하려고 했음.

 2. index를 얻었을 때, 해당 Node로 접근하기 위해서 편법인 List를 사용하자.

 3. ListNode를 2번 탐색하는 것을 1번으로 줄이다.

class Solution {
    public ListNode middleNode(ListNode head) {
        int count = 0;
        List<ListNode> list = new ArrayList();
        while(true){
            count++;
            list.add(head);
            if(head.next == null){
                break;
            }else{
                head = head.next;    
            }
        }
        return list.get(count/2);
    }
}

6. 다른 사람이 작성한 알고리즘 보기

 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        if(head == null){
            return head;
        }
        
        ListNode slow = head;
        ListNode fast = head;
        
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

 

7. 다른 사람이 작성한 알고리즘을 보고 배운점

 - slow는 1칸씩, Fast가 마지막에 닿을 때, slow는 절반을 가는 알고리즘이다.

 - 별도의 자료구조 없이, ListNode 하나를 통해서 결과값을 얻을 수 있다.

 - 주어진 input에 대한 자료구조에 의해서 깔끔하게 값을 처리하는 것을 항상 생각하자.

 - Node는 next와 next.next로 속도 조절을 한다고 생각하자.

 

문제 : https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/529/week-2/3290/

Account Login - LeetCode

다른 사람의 알고리즘 : https://medium.com/@saurav.agg19/middle-of-the-linked-list-884161301014

Middle of the Linked List