항해99 2주차 - 역순 연결 리스트

Today I learned
2022/01/17

회고록

1/17

항해 99, 알고리즘 1주차

교재 : 파이썬 알고리즘 인터뷰

8장 연결 리스트

1. 이론

링크드 리스트란?

연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.

노드 구현

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

링크드 리스트 구현

class LinkedList:
    def __init__(self, data):
        self.head = Node(data)
    
    #헤더부터 탐색해 뒤에 새로운 노드 추가하기
    def append(self, data):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(data)
	
    #모든 노드 값 출력
    def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next

노드 인덱스 알아내기

    def get_node(self, index):
        cnt = 0
        node = self.head
        while cnt < index:
            cnt += 1
            node = node.next
        return node

삽입

    def add_node(self, index, value):
        new_node = Node(value)
        if index == 0:
            new_node.next = self.head
            self.head = new_node
            return
        node = self.get_node(index-1)
        next_node = node.next
        node.next = new_node
        new_node.next = next_node

[5] -> [12] -> [8]를 [5] -> [6] -> [12] -> [8] 만들기 위해서 인덱스 1자리인 12에 들어가기 위해 5 노드 위치를 파악하고, 그 다음 next에 6 노드를 연결한다. [6]의 next는 12가 연결되게끔 해야한다.

삭제

    def delete_node(self, index):
        if index == 0:
            self.head = self.head.next
            return
        node = self.get_node(index-1)
        node.next = node.next.next

삭제하는 것은 더 간단한다. [5] -> [6] -> [12] -> [8]에서 삭제하고자 하는 index 번 째 노드의 전 노드를 찾아 바로 다음 노드가 될 것을 연결해주면 된다.

[5] -> [12] -> [8]
----[6]----

위처럼 1번째 노드인 [6]을 삭제하고자 한다면, 그 전 노드인 [5]의 next를 바로 [12]와 연결해주면 된다.

2. 문제

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Example 2:

Input: head = [1,2]
Output: [2,1]
Example 3:

Input: head = []
Output: []

Constraints:

The number of nodes in the list is the range [0, 5000].
-5000 <= Node.val <= 5000

https://leetcode.com/problems/reverse-linked-list/

3. MySol

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def reverseLL(head: ListNode):
    curr = head
    print('head : ' + str(head.val))
    prev = None

    while curr is not None:
        print('curr : ' + str(curr.val) + ', curr.next : ' + str(curr.next))
        temp = curr.next
        curr.next = prev
        prev = curr
        curr = temp

    return prev


if __name__ == '__main__':

    fifth_node = ListNode(5,None)
    fourth_node = ListNode(4,fifth_node)
    third_node = ListNode(3,fourth_node)
    second_node = ListNode(2,third_node)
    first_node = ListNode(1,second_node)

    result = reverseLL(first_node)

    while (True):
        print('result : ' + str(result.val))
        result = result.next

4. 배운 점

• 노드와 노드에 해당하는 head, prev, value
• 해당 문제는 single linked list를 이용하는 문제이며 single은 prev라는 존재가 없이 하나만 연결되어있는데, solution의 prev는 head를 대체하게 되는 link이다.

5. 총평

링크드리스트 구조 이해