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. 문제
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Example 1:
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:
Input: list1 = [], list2 = []
Output: []
Example 3:
Input: list1 = [], list2 = [0]
Output: [0]
Constraints:
The number of nodes in both lists is in the range [0, 50].
-100 <= Node.val <= 100
Both list1 and list2 are sorted in non-decreasing order.
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 merge_with_sort(list1: ListNode, list2: ListNode):
list = []
curr = list1
curr2 = list2
while True:
if curr is None:
list.append(curr2.val)
curr2=curr2.next
elif curr2 is None:
list.append(curr.val)
curr=curr.next
elif curr.val == curr2.val :
list.append(curr.val)
list.append(curr2.val)
curr=curr.next
curr2=curr2.next
elif curr.val < curr2.val :
list.append(curr.val)
curr=curr.next
else :
list.append(curr2.val)
curr2=curr2.next
if curr is None and curr2 is None:
break
return list
if __name__ == '__main__':
arr2_third_node = ListNode(4, None)
arr2_second_node = ListNode(3, arr2_third_node)
arr2_first_node = ListNode(1, arr2_second_node)
arr1_third_node = ListNode(3,None)
arr1_second_node = ListNode(2,arr1_third_node)
arr1_first_node = ListNode(1,arr1_second_node)
result = merge_with_sort(arr1_first_node, arr2_first_node)
print('result : ' + str(result))
4. 배운 점
- 책에는 재귀를 이용한 풀이가 나와 있으나, 아직은 재귀훈련이 익숙치 않아 각 조건문별로 로직을 구현하여 반복문을 돌렸다.
5. 총평
리스트, 반복문 훈련
