LeetCode - 876. Middle of the Linked List

https://leetcode.com/problems/middle-of-the-linked-list/?envType=study-plan&id=level-1 

 

내 첫번째 풀이

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 예외처리
        if head==None or head.next==None:
            return head
        
        mid = head # 지금까지의 middle node
        cur = head # 커서 : 맨 앞에서부터 한칸씩 뒤로 훑으며 넘어가는 커서 역할을 해줄 포인터
        cur_idx = 1 # 1부터 시작하는 인덱스임
        mid_idx = 1 # 얘도 1부터 시작하는 인덱스
        
        while cur.next!=None:
            cur = cur.next
            cur_idx+=1
            mid_idx_to_be = cur_idx//2 + 1  # 나누기 2 해서 +1 
            loopNum = mid_idx_to_be - mid_idx
            for i in range(loopNum):
                mid = mid.next
            mid_idx =  mid_idx_to_be
            
        
        return mid

 

상위 70퍼라 퍼포먼스가 썩 그리 좋진 않음,,

 

내 두번째 풀이

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 예외처리
        if head==None:
            return head
        
        mid = head # 지금까지의 middle node
        cur = head # 커서 : 맨 앞에서부터 한칸씩 뒤로 훑으며 넘어가는 커서 역할을 해줄 포인터
        cur_idx = 1 # 1부터 시작하는 인덱스임
        mid_idx = 1 # 얘도 1부터 시작하는 인덱스
        
        while cur.next!=None:
            cur = cur.next
            cur_idx+=1
            mid_idx_to_be = cur_idx//2 + 1  # 나누기 2 해서 +1 
            loopNum = mid_idx_to_be - mid_idx
            for i in range(loopNum):
                mid = mid.next
            mid_idx =  mid_idx_to_be
            
        
        return mid

예외처리 부분 기존 두번째 조건문은 어짜피 아래 로직으로도 충분히 걸러질 수 있어서 뺐더니 아주 조금 나아짐

상위 40퍼 정도.. 그치만 아직 부족 ㅠ

 

 

세번째 풀이

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 예외처리
        if head==None:
            return head
        elif head.next==None:
            return head
        
        mid = head # 지금까지의 middle node
        cur = head # 커서 : 맨 앞에서부터 한칸씩 뒤로 훑으며 넘어가는 커서 역할을 해줄 포인터
        cur_idx = 1 # 1부터 시작하는 인덱스임
        mid_idx = 1 # 얘도 1부터 시작하는 인덱스
        
        while cur.next!=None:
            cur = cur.next
            cur_idx+=1
            mid_idx_to_be = cur_idx//2 + 1  # 나누기 2 해서 +1 
            loopNum = mid_idx_to_be - mid_idx
            for i in range(loopNum):
                mid = mid.next
            mid_idx =  mid_idx_to_be
            
        
        return mid

오잉,, 혹시나 해서 아까 위에서 삭제한 조건문을 다시 넣고 대신 or로 묶어 넣는게 아니라 if 하고 elif 로 나눠서 넣었더니.. 

퍼포먼스 몰라보게 달라짐 ;ㅅ;

상위 0.02프로,, 짜릿 +_+

 

 

 

---

참고

hare and tortoise algorithm

/**
 * hare and tortoise algorithm
 */
function middleNode(head: ListNode | null): ListNode | null {
    // initialize hare and tortoise with first linked list node
    let hare: ListNode = head;
    let tortoise: ListNode = head;

    while(true) {
        if (hare === null || hare.next === null) {
            break;
        }
        hare = hare.next.next;
        tortoise = tortoise.next;
    }

    return tortoise;
};

1/3지점이면 3배씩 뛰고,,,,

-> 끝을 알 수 없지만 중간의 어떤 지점을 알아야 할때 유용하게 사용할 수 있는 알고리즘!!!