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, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.
The first node is considered odd, and the second node is even, and so on.
Note that the relative order inside both the even and odd groups should remain as it was in the input.
You must solve the problem in O(1) extra space complexity and O(n) time complexity.
Example 1:
Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]
Example 2:
Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]
Constraints:
n == number of nodes in the linked list
0 <= n <= 10^4
-10^6 <= Node.val <= 10^6
https://leetcode.com/problems/odd-even-linked-list/
3. MySol
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def oddEvenLL(head: ListNode):
if head is None:
return None
headForReturn = head
secondStartingPoint = head.next
secondCurr = secondStartingPoint
curr = head
while curr is not None:
temp = curr.next
if curr.next is not None:
curr.next = curr.next.next
secondCurr.next = temp
secondCurr = secondCurr.next
secondCurr.next = None
else:
curr.next = secondStartingPoint
break
if curr.next is not None:
curr = curr.next
return headForReturn
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 = oddEvenLL(first_node)
while (True):
print('result : ' + str(result.val))
if result.next is None:
break
result = result.next
4. 배운 점
- 반복문을 이용한 구현
- 내 풀이가 책과 코드는 다르지만 동일한 방식의 풀이가 나왔다
5. 총평
리스트, 반복, 조건문 훈련
