[알고리즘] Leetcode-연결리스트

팰린드롬 연결 리스트

• Palindrome Linked List
• 연결 리스트가 팰린드롬 구조인지 판별하라

• 입력 & 출력 예시
  

• 풀이) Runner 기법 : fast runner는 2칸씩 slow runner가 1칸씩 이동하면, slow runner는 딱 절반을 가게 된다. 그 때 비교하며 계산

  # Definition for singly-linked list.
  # class ListNode:
  #     def __init__(self, val=0, next=None):
  #         self.val = val
  #         self.next = next
  class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        rev = None 
        slow = fast = head
          
        # runner를 이용해 reversed 연결 리스트 구성 
        while fast and fast.next:
            fast = fast.next.next
            rev, rev.next, slow = slow, rev, slow.next
              
        if fast:
            slow = slow.next
          
        # 팰린드롬 확인 
        while rev and rev.val == slow.val:
            slow, rev = slow.next, rev.next
          
        return not rev
  

두 정렬 리스트의 병합

• 21. Merge Two Sorted Lists
• 정렬되어 있는 두 연결 리스트를 합쳐라
• 입력 & 출력 예시

  Input: list1 = [1,2,4], list2 = [1,3,4]
  Output: [1,1,2,3,4,4]
  

• 풀이) 재귀 구조로 연결

  # Definition for singly-linked list.
  # class ListNode:
  #     def __init__(self, val=0, next=None):
  #         self.val = val
  #         self.next = next
  class Solution:
    def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[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
  

역순 연결 리스트

• 206. Reverse Linked List
• 연결 리스트를 뒤집어라
• 입력 & 출력 예시
  
• 풀이) 반복문으로 뒤집기

  # Definition for singly-linked list.
  # class ListNode:
  #     def __init__(self, val=0, next=None):
  #         self.val = val
  #         self.next = next
  class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        node, prev = head, None 
        while node:
            next, node.next = node.next, prev
            prev, node = node, next
          
        return prev
  

  

역순 연결 리스트 II

• 92. Reverse Linked List II
• 인덱스 left에서 right까지를 역순으로 만들어라. left는 1부터 시작한다.
• 입력 & 출력 예시
  
• 풀이) 반복 구조로 노드 뒤집기

  # Definition for singly-linked list.
  # class ListNode:
  #     def __init__(self, val=0, next=None):
  #         self.val = val
  #         self.next = next
  class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        # exception 
        if not head or left == right:
            return head
          
        root = start = ListNode(None)
        root.next = head
          
        # start, end 지정 
        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