📌 13) 팰린드롬 연결 리스트 ( 234. Palindrome Linked List )
✔ 풀이 (deque 데크 이용)
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
from collections import deque
class Solution(object):
def isPalindrome(self, head):
#node의 값들을 deque자료형에 추가
node_dq = deque()
node, node_dq = head, deque()
while node is not None:
node_dq.append(node.val)
node = node.next
#팰린드롬 판별
while len(node_dq) > 1:
if node_dq.popleft() != node_dq.pop():
return False
return True✔ 풀이 (runner 런너 이용)
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
from collections import deque
class Solution(object):
def isPalindrome(self, head):
rev = None
fast = slow = head
while fast and fast.next: #fast가 끝까지 갈때까지
fast = fast.next.next
rev, rev.next, slow = slow, rev, slow.next
#홀수개의 node를 가지고 있으면 fast != None
#짝수개의 node를 가지고 있으면 fast = None
if fast: #홀수개의 node를 가지고 있을 경우
slow = slow.next #slow를 이동시켜 중간값은 비교하지 않도록 한다.
#팰린드롬 여부 확인
while rev and rev.val == slow.val:
rev, slow = rev.next, slow.next
return not rev📌 14) 두 정렬 리스트의 병합 ( 리트코드 21. Merge Two Sorted Lists )
✔ 풀이 (재귀 구조로 연결)
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def mergeTwoLists(self, l1, l2):
# not l1 => l1이 None 일때 스왚(마지막 노드의 next는 None 이므로)
# l2 and l1.val > l2.val
#=> l2가 존재해야 l2.val이 존재하기 때문에 l2가 존재하는 부분 추가확인
if (not l1) or (l2 and l1.val > l2.val):
l1, l2 = l2, l1
if l1: #l1이 None이 아닐 경우
l1.next = self.mergeTwoLists(l1.next, l2)
return l1 #l1이 None이 되면 재귀 끝. return 시작하고 백트래킹되면서 엮임📌 15) 역순 연결 리스트 ( 리트코드 206. Reverse Linked List )
✔ 풀이 (재귀 구조로 뒤집기)
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def reverseList(self, head):
def reverse(node, prev = None):
if not node: #node = None 일 경우 역순연결리스트(prev)완성 이므로 반환
return prev
#next에 .next할당 / node.next에 역순연결리스트 완성 된 부분 연결
next, node.next = node.next, prev
return reverse(next, node)
return reverse(head)
✔ 풀이 (반복 구조로 뒤집기)
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def reverseList(self, head):
node, prev = head, None
while node:
#next 변수에 node.next할당
#node.next에 현재까지 완성 된 역순연결리스트 할당
next, node.next = node.next, prev
prev = node #node까지 추가해서 완성 된 역순연결리스트 재할당
#아직 역순연결리스트가 되지 않은 부분(next)를 node에 할당하여 None이 될때까지 반복
node = next
return prev📌 16) 두 수의 덧셈 ( 리트코드 2. Add Two Numbers )
✔ 풀이 (자료형 변환)
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def addTwoNumbers(self, l1, l2):
#역순 연결리스트 반환
def reverse_linkedlist(head):
node, prev = head, None
while node:
next, node.next = node.next, prev
node, prev = next, node
return prev
#연결리스트를 리스트로 반환
def to_list(head):
val_list = []
node = head
while node:
val_list.append(node.val)
node = node.next
return val_list
#문자열을 연결리스트로 반환
def to_linkedlist(str_num):
head = ListNode(str_num[0])
node = head
for i in range(1, len(str_num)):
node.next = ListNode(str_num[i])
node = node.next
return head
num1 = int(''.join([ str(n) for n in to_list(reverse_linkedlist(l1))]))
num2 = int(''.join([ str(n) for n in to_list(reverse_linkedlist(l2))]))
sum = num1 + num2
return reverse_linkedlist(to_linkedlist(str(sum)))📝 숫자형 리스트를 단일 값으로 병합하는 방법
✔ 풀이 (전가산기 구현)
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
#l1, l2는 순서 그래로 앞에서 부터 계산하고 올림은 그 다음으로 올리면
#따로 역순을 구해 계산하지 않아도 됨.
class Solution(object):
def addTwoNumbers(self, l1, l2):
head = node = ListNode(0)
carry = 0 #자리올림 수
while l1 or l2 or carry:
sum = 0
if l1:
sum += l1.val
l1 = l1.next
if l2:
sum += l2.val
l2 = l2.next
carry, val = divmod(sum + carry, 10)
node.next = ListNode(val) #node의 다음에 연결
node = node.next #다음 노드를 가르킴
return head.next #head는 0, None 이기 때문에 그 다음 노드를 반환 📌 17) 페어의 노드 스왑 ( 리트코드 24. Swap Nodes in Pairs )
✔ 풀이 (값만 교환)
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def swapPairs(self, head):
node = head
while node and node.next:
node.val, node.next.val = node.next.val, node.val
node = node.next.next
return head✔ 풀이 (반복 구조로 스왑)
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def swapPairs(self, head):
root = prev = ListNode(None)
prev.next = head
while head and head.next:
second_n = head.next
head.next = second_n.next #head의 다음 다음을 가르키도록 연결
second_n.next = head #두번째 노드가 첫번째 노드를 가르키도록 연결
#이전 노드들이 두번째 노드를 가르키도록 연결
prev.next = second_n
#다음 노드들을 swap하기 위해 head와 prev이동
#head는 이미 두번째 노드로 이동했으므로 한번만 next하면 다음번에 swap할 첫번째 노드가 됨
head = head.next
prev = prev.next.next
return root.next
✔ 풀이 (재귀 구조로 스왑)
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def swapPairs(self, head):
if head and head.next:
p = head.next #두번째 노드를 지정
head.next = self.swapPairs(p.next) #첫번째 노드가 다음 다음을 가르키도록 하는데, 재귀함수로 백트래킹되면서 연결됨
p.next = head #두번째 노드가 첫번째 노드를 가르키도록 함
return p
return head📝 재귀풀이는 불필요한 변수를 사용하지 않아 공간 복잡도가 낮고, 코드가 빈틈이 없이 짜임새가 있음 (우아한 풀이)
📌 18) 홀짝 연결 리스트 ( 리트코드 328. Odd Even Linked List )
✔ 풀이 (반복 구조로 홀짝 노드 처리)
class Solution(object):
def oddEvenList(self, head):
#예외처리 (노드의 개수 n의 최솟값은 0 => 다음 로직을 처리하려면 적어도 한개의 노드가 필요함)
if not head:
return head
odd = head #홀수번째 노드
even_head = even = head.next #짝수번째 노드
while even and even.next:
#각각 다음 홀수, 짝수 번째 노드와 연결하고 이동
odd.next, even.next = odd.next.next, even.next.next
odd, even = odd.next, even.next
odd.next = even_head #홀수번째 노드의 마지막을 짝수번째 노드의 처음과 연결
return head📌 19) 역순 연결 리스트2 ( 리트코드 92. Reverse Linked List II )
✔ 풀이 (반복 구조로 노드 뒤집기)
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def reverseBetween(self, head, left, right):
root = start = ListNode(None)
root.next = head
#start를 역순으로바꿔야할 첫 시작 위치의 바로 앞을 가리키도록 이동
for _ in range(left - 1):
start = start.next
end = start.next #역순으로 바꿨을때 가장 마지막에 올 노드
for _ in range(right - left):
tmp, start.next, end.next = start.next, end.next, end.next.next
start.next.next = tmp
return root.next