항해99 알고리즘 2회차

싱글 링크드 리스트

 

1. 링크드리스트, 노드가 있는데 링크드리스트에 노드를 이용하여 노드끼리 연결을 해주는 역할

2. head와 tail에 노드가 들어가서 연결

3. head 첫 번째 노드 역할, taild 마지막 노드 역할

4. 단일 링크드리스트는 전 노드를 구해서 삭제를 해준다. (더블 링크드 리스트는 쉽다.)

 

링크드리스트에 head, tail 생성 후 연결해서 이어주거나 삭제할 때 많이 헷갈렸다

 

노드에 next, prev을 넣으면 더블 링크드 리스트

tail을 head에 이어주면 순환 링크드 리스트

 

# 노드
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


# 단일 링크드리스트
class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    # 마지막 삽입
    def append(self, data):
        new_node = Node(data)  # 노드 생성

        if self.head is None:
            self.head = new_node
        else:
            self.tail.next = new_node

        self.tail = new_node

    # 첫번째 삽입
    def prepend(self, data):
        new_node = Node(data)

        if self.head is None:
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head = new_node

    # 삭제
    def remove(self, data):
        linked = self.head
        prev_node = None

        while linked is not None:
            if linked.data == data:

                if self.head == linked:
                    self.head = linked.next

                if self.tail == linked:
                    self.tail = prev_node

                prev_node.next = linked.next
                linked = None

            prev_node = linked

            if linked is not None:
                linked = linked.next


temp = SinglyLinkedList()
temp.append(1)
temp.append(2)
temp.append(3)
temp.prepend(99)
temp.append(4)
temp.prepend(98)
temp.remove(3)

iterator = temp.head

while iterator is not None:
    print(iterator.data)
    iterator = iterator.next

---

역순 연결 리스트 https://leetcode.com/problems/reverse-linked-list/

 

회고

처음에 linkedList를 구현해야 하는 줄 알고 삽질을 좀 했었다.

역방향으로 가야하는 문제 였는데 노드 연결의 방향성을 반대로 바꾼다는 생각을 못했다.

 

참고 유튜브

https://www.youtube.com/watch?v=gf_BiXt4YlQ

    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        prev = None
        curr = head

        while curr is not None:
            temp = curr.next # 다음 노드 저장
            curr.next = prev # 방향을 이전 노드로 수정
            prev = curr # 이전 노드 저장
            curr = temp # 다음 노드 진행

        return prev

---

두 정렬 리스트의 병합 https://leetcode.com/problems/merge-two-sorted-lists/

 

접근 방식

1. 반복문을 2번 사용하여서 병합을 하려고 했지만

2. ListNode를 선언해서 비교해서 넣기만 하려고 했지만 불필요한 값도 들어가고 기존 것은 연결이 되어있으니 생각한 대로 안 됐다.

 

틀린 결과

# 값을 비교 해야한다.
# 맞으면 채워 넣는다.
result = ListNode()
while list1 is not None: # 3
    while list2 is not None: # 3*3

        # 1->1->3->4
        if list1.val == list2.val:
            result.next = list1
            result.next.next = list2

        list2 = list2.next

    list1 = list1.next

return result

 

맞은 결과 - 파이썬 알고리즘 인터뷰 책

 

1. 재귀함수로 진행한다.

2. list1이 더 클 경우에만 스위칭을 해준다.

3. list1이면 list2를 담고 반복한다

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    if (not list1) or (list2 and list1.val > list2.val):
        list1, list2 = list2, list1
    if list1:
        list1.next = self.mergeTwoLists(list1.next, list2)
    return list1

 

맞은 결과 - 블로그 해답

 

1. 더미 ListNode를 생성하고

2. list1, list2를 값을 비교하면서 넣어준다.

3. 남아 있는 list1, list2를 삼항연산자로 비교 후 넣어주고

4. return에는 처음에 더미 생성 시 -1을 넣었기에 dummy.next를 한다.

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:

    dummy = ListNode(-1)
    curr = dummy

    while list1 is not None and list2 is not None:

        if list1.val < list2.val:
            curr.next = list1
            list1 = list1.next
        else:
            curr.next = list2
            list2 = list2.next

        curr = curr.next

    curr.next = list1 if list1 is not None else list2

    return dummy.next

---

홀짝 연결 리스트 https://leetcode.com/problems/odd-even-linked-list/

 

접근 방식

더미를 2개 만들어서 val을 기준으로 홀, 짝 나눠서 넣어서 이으려고 했지만

next가 연결되어있어서 무한 사이클이 돌기 때문에 실패

 

틀린 결과

def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:

    dummy = ListNode(-1)
    curr = dummy

    dummy2 = ListNode(-1)
    curr2 = dummy2

    while head is not None:

        if head.val % 2 != 0:
            curr.next = head
            curr = curr.next
        else:
            curr2.next = head 
            curr2 = curr2.next

        head = head.next

    curr.next = dummy2.next
    return dummy2.next

 

맞은 결과 - GPT

 

1. head의 next를 수정

2. 홀수에는 짝수를, 짝수에는 홀수를 지정해 준다

3. 각자 next를 지정해준다.

def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:

    if head is None:
        return head

    odd = head # 1
    even = head.next # 2
    evenHead = even # 2

    while even and even.next: # 홀수일때만 반복
        odd.next = even.next # 홀수의 다음은 짝수의 다음 1->3
        odd = even.next # 3

        even.next = odd.next # 짝수의 다음은 홀수 2->4
        even = odd.next # 4

    odd.next = evenHead # 이어준다

    return head

 

맞은 결과 - 유튜브 https://www.youtube.com/watch?v=WoUAs7R3Ao4

 

위에는 이해하는데 헷갈렸는데

간단하게 next.next로 편하게 해주는 방향도 있었다.

def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:

    if head is None:
        return head

    odd = head
    even = head.next
    evenHead = even

    while even and even.next:
        odd.next = odd.next.next
        odd = odd.next

        even.next = even.next.next
        even = even.next

    odd.next = evenHead # 이어준다

    return head