[Python] Linked List (2)

 

Problem 14. Merge Two Sorted Lists

https://leetcode.com/problems/merge-two-sorted-lists/

 

Solution 1. 재귀 구조

 

def merge_two_lists(self, l1: ListNode, l2: ListNode) -> ListNode:
    if (not l1) or (l2 and l1.val > l2.val):
        l1,l2 = l2,l1
    if l1:
        l1.next = self.mergeTwoLists(l1.next, l2)
    return l1

 

---

Problem 15. Reverse Linked Lists

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

 

Solution 1. 재귀 구조

 

def reverse_list(self, head: ListNode) -> ListNode:
    def reverse(node: ListNode, prev: ListNode = None):
        if not node:
            return prev
        next, node.next = node.next, prev
        return reverse(next, node)
    return reverse(head)

 

---

Solution 2. 반복 구조

 

def reverse_list(self, head: ListNode) -> ListNode:
    node, prev = head, None
    
    while node:
        next, node.next = node.next, prev
        prev, node = node, next
    return prev

 

---

Problem 16. Add Two Numbers

https://leetcode.com/problems/add-two-numbers/

 

Solution 1. 자료형 변환

 

class Solution:
    # 연결리스트 뒤집기
    def reverse_list(self, head: ListNode) -> ListNode:
        node, prev = head, None
        
        while node:
            next, node.next = node.next, prev
            prev, node = node, next
        return prev
    
    # 연결리스트를 파이썬 리스트로 변환
    def to_list(self, node: ListNode) -> ListNode:
        list: List = []
        while node:
            list.append(node.val)
            node = node.next
        return list
    
    # 파이썬 리스트를 연결 리스트로 변환
    def to_reversed_linked_list(self, result: ListNode) -> ListNode:
        prev: ListNode = None
        for r in result:
            node = ListNode(r)
            node.next = prev
            prev = node
        return node
    
    # 두 연결 리스트의 덧셈
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        a = self.to_list(self.reverse_list(l1))
        b = self.to_list(self.reverse_list(l2))
        
        result_str = int(''.join(map(str, a))) + int(''.join(map(str, b)))
        
        # 최종 계산 결과 연결 리스트 변환
        return self.to_reversed_linked_list(str(result_str))

 

 

---

Solution 2. 내 풀이 방식 : eval의 활용

python에는 문자열을 바로 계산식으로 인식할 수 있는 eval이 있다.
따라서 연결 리스트를 여러번 변환하고 int로 타입 변경해주는 과정을 줄이기 위해 만든 풀이방식이다.

 

# 연결 리스트 a,b를 리스트로 변경
# join으로 묶인 str 타입의 숫자를 [::-1]로 뒤집고, eval로 더한다
# int로 변경 후 연결리스트로 프린트

class Solution:
    # 연결리스트를 파이썬 리스트로 변환
    def to_list(self, node: ListNode) -> ListNode:
        list: List = []
        while node:
            list.append(node.val)
            node = node.next
        return list
    
    # 파이썬 리스트를 연결 리스트로 변환
    def to_reversed_linked_list(self, result: ListNode) -> ListNode:
        prev: ListNode = None
        for r in result:
            node = ListNode(r)
            node.next = prev
            prev = node
        return node
    
    # 두 연결 리스트의 덧셈
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        # 두 연결리스트의 리스트화
        a = self.to_list(l1)
        b = self.to_list(l2)
        
        # 리스트의 덧셈
        result_str = eval(''.join(map(str, a))[::-1] + '+' + ''.join(map(str, b))[::-1])
        
        # 최종 계산 결과 연결 리스트 변환
        return self.to_reversed_linked_list(str(result_str))

 

 

---

Problem 17. Swap Nodes in Pairs

https://leetcode.com/problems/swap-nodes-in-pairs/

 

Solution 1. 변칙적 풀이 : 값만 교환

 

def swap_pairs(self, head: ListNode) -> ListNode:
    curr = head
    
    while curr and curr.next:
        # 값만 스왑
        curr.val, curr.next.val = curr.next.val, curr.val
        curr = curr.next.next # 두번 건너 뛰므로 2개씩 묶어서 교환됨
    return head

 

---

Solution 2. 반복 구조로 풀이

 

def swap_pairs(self, head: ListNode) -> ListNode:
    root = prev = ListNode(None)
    prev.next = head
    while head and head.next:
        # b가 a(head)를 가르키도록 할당
        b = head.next
        head.next = b.next
        b.next = head
        
        # prev가 b를 가리키도록 할당
        prev.next = b
        
        # 다음 턴을 위해 이동
        head = head.next
        prev = prev.next.next
    return root.next

 

 

출처 : 파이썬알고리즘인터뷰