[1스4코2파] #129. LeetCode Algorithm Day 5 (876. Middle of the Linked List, 19. Remove Nth Node From End of List)

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코2파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (129일차)
[4코1파] 2023.01.13~ (120일차)
[1스4코1파] 2023.04.12~ (31일차)
[1스4코2파] 2023.05.03 ~ (10일차)

Today :

2023.05.12 [129일차]

LeetCode Algorithm Day 5
876. Middle of the Linked List

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

19. Remove Nth Node From End of List

• https://leetcode.com/problems/remove-nth-node-from-end-of-list/?envType=study-plan&id=algorithm-i

문제 1

[876] Middle of the Linked List
https://leetcode.com/problems/middle-of-the-linked-list/?envType=study-plan&id=algorithm-i

내 코드

# 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]:
        n, nHead, half = 0, head, 0
        while nHead.next:
            nHead = nHead.next
            n +=1

        half = n//2 + n%2

        while half>0:
            head = head.next
            half -= 1
        
        return head

문제 풀이 방법

위의 연결형 리스트에 접근하는 클래스의 메소드가 next로 접근해야 하는 걸 첨봐서 이거 뭐지 하고 봤던 문제였던 것이다... 자료구조에서 리스트 공부할 때 단방향, 양방향 리스트를 보긴했는데 single liked list 문제는 사실 풀어 본 적이 없어서 새로웠음

뭐 나는 일단 n과 head를 그대로 copy한 nhead 변수를 만들고
nhead 에서 next 메소드를 통해서 일방향 리스트의 element들 만큼 n을 더해줘서
head의 길이를 구했다.

그리고 추후에 n의 절반 half 변수를 이용해서, 홀수와 짝수를 몫, 나머지를 이용해서 half의 index를 구했고, 다시 한번 head를 while문으로 next로 접근하면서,
half를 가감해서 half 가감이 끝나면(half >0) 그 뒤에 있는 리스트의 원소만 보여주게끔 풀었다

증빙

---

문제 2

[19] Remove Nth Node From End of List
https://leetcode.com/problems/remove-nth-node-from-end-of-list/?envType=study-plan&id=algorithm-i

내 코드

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:

        tmpList = ListNode(0)
        tmpList.next = head
        start, end = tmpList, tmpList

        for i in range(n):
            start = start.next

        while start.next!=None:
            start = start.next
            end= end.next

        end.next = end.next.next

        return tmpList.next

문제 풀이 방법

single-linked list 위의 Node Class의 next method를 잘 활용했어야 하는데,
역시나 Single-linked list 문제는 잘 안풀어봐서 헷갈림
two pointer 로 start, end 로 노드들을 할당하면서 비교했다가
기존의 head의 next 메소드로 다시 return

증빙

여담

마참내 ! 오늘 금요일!
Machamne ! today is Friday~!