연결리스트

* 펠린드롬 연결리스트

연결리스트가 펠린드롬 구조인지 판별하여라

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

---

'''
펠린드롬 = 뒤집어도 같아야함

연결리스트가 펠린드롬 구조인지 판별하여라

1. 리스트를 이용하여 앞뒤 비교 = pop(0)?pop()
2. fast, slow runner활용
2.1 fast가 끝까지 가면 slow는 절반만큼 가게됨
2.2 slow는 이동하면서 역순으로 rev에 값을 저장
2.3 rev와 남은 slow가 가야하는 부분을 비교
2.4 홀수개일 경우 중앙값을 포함하면 안된다. 따라서 slow를 한칸 더 옮긴다.

'''
# 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:
        '''
        q = []
        q: Deque = collecitons.deque()

        if not head:
            return True

        node = head

        #리스트 변환
        while node is not None:
            q.append(node.val)
            node = node.next

        #펠린드롬 변환
        while len(q) > 1:
            if q.pop(0) != q.pop():
                return False
        return True
        '''

        if not head:
            return True

        fast = slow = head
        rev = None

        #절반만큼 이동/ 펠린드롬이 짝수 or 홀수 이므로 fast, fast.next값을 비교
        while fast and fast.next:
            #fast는 두칸씩 이동
            fast = fast.next.next
            #slow는 한칸씩 이동, rev에 역순으로 값 저장
            rev, slow, rev.next = slow, slow.next, rev

        #짝수일 경우 fast의 값은 None이 되고 홀수일 경우 값을 가지게 된다.
        if fast:
            slow = slow.next
        #rev와 남은 값 비교
        while rev and rev.val == slow.val:
            slow, rev = slow.next, rev.next

        #모든 값이 맞다면 rev는 none일 것이다.
        return not rev

 

 

 

 

* 정렬되어 있는 두 연결 리스트를 합쳐라

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

---

'''
정렬되어 있는 두 연결 리스트를 합쳐라

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

방법1)
1번째 연결리스트를 기준으로 두고 2번째 연결리스트의 값을 비교하여 삽입
1번째 연결리스트의 값과 같거나 크면 뒤로, 작으면 앞으로 => n^2만큼 비교해야..

방법2)
두 연결리스트를 합친뒤 정렬하기
정렬방법.. merge sort로 (nlogn)

'''

# 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]:

        #l1이 l2보다 크면 swap => 재귀로 반복
        if (not l1) or (l2 and l1.val > l2.val):
            l1, l2 = l2, l1

        #l1이 none 아니면, 재귀 호출
        if l1:
            l1.next = self.mergeTwoLists(l1.next, l2)

        return l1

 

 

 

 

* 연결리스트를 뒤집어라

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

---

'''
연결리스트를 뒤집어라

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

방법1)
러너문제 활용
rev, rev.next, slow = slow, rev, slow.next

방법2)
재귀활용
rev에 저장하게..

반복문을 사용하는것이 공간복잡도가 낮고 시간도 빠르다..

'''


# 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]:

        result = None
        temp = head

        while temp:
            temp, result, result.next = temp.next, temp, result

        return result


        '''
        def reverse(temp: ListNode, rev: ListNode = None):

            if not temp:
                return rev

            rev, temp, rev.next = temp, temp.next, rev

            return reverse(temp, rev)

        return reverse(head)
        '''

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

다시....

 

 

 

 

* 홀짝 연결 리스트

연결리스트를 홀수 노드 다음에 짝수 노드가 오도록 재구성하라. 공간 복잡도 O(1), 시간 복잡도 O(n)에 풀이하라.

https://leetcode.com/problems/odd-even-linked-list/

---

nput: head = [1,2,3,4,5]
Output: [1,3,5,2,4]

Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]

홀수번째 노드가 짝수번째 노드 뒤에 와야한다.

방법1) 리스트로 바꾸고 슬라이싱으로 처리...는 파이썬 내장 함수로 간단...

방법2) 홀수, 짝수 노드 따로 구분하여 붙이기
1->2->3->4->5

1. 1->3
2. 2->4
3. 3->5
4. 5->2
   odd = 1->3->5
   even = 2->4
5. 1->3->5->2->4

체크
=> a.next 가 null인가? 확인
=> 2->4노드에서 4->null이 되어야함

홀: odd.next = (even.next = odd.next.next)
짝: even.next = (odd.next = even.next.next)

시작
odd : head
even : head.next

마지막

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

        if head is None:
            return head

        #odd, even으로 구분
        odd = odd_start = head
        even = even_start = head.next


        #while odd and odd.next:이 아니라 even을 비교하여야한다... odd일 경우 None.next에 값을 넣게 되버림(한번에 두개씩 바꾸므로)

        while even and even.next:
            odd.next, even.next = even.next, even.next.next
            #odd를 다음 odd로, even을 다음 even으로
            odd = odd.next
            even = even.next

        #odd->even 연결
        odd.next = even_start

        return odd_start