# CSPT25 Lecture 9

## Delete a Node

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    """
    1-->2-->3 remove node 2
    1-->3
    
    1-->2-->3 remove node 1
    2-->3
    
    Plan
    Copy the next node's value to the node given, then skip that next node to remove
    the duplicate
    """
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        curr = node
        curr.val = curr.next.val
        curr.next = curr.next.next

## 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:
    """
    1->2->3->4
    4->3->2->1
    
    1
    1
    
    3->3->3
    3->3->3
    
    None
    None
    
    Runtime: O(n)
    Space: O(1)
    """
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        curr = head
        prev = None
        while curr != None:
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp
        return prev

## Odd Even LinkedList

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    """
    a->b->c->d->e
    a->c->e->b->d
    
    a->b->c
    a->c->b
    
    a
    a
    
    a->b
    a->b
    
    Plan
    Build an oddList and an evenList using the dummyhead pattern
    Append the evenList to the tail of the oddList
    Return oddListDummyHead.next
    """
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head == None:
            return None
        oddDummyHead = ListNode(-1)
        oddCurr = oddDummyHead
        evenDummyHead = ListNode(-1)
        evenCurr = evenDummyHead
        counter = 1
        curr = head
        while curr != None:
            if counter % 2 == 0:
                evenCurr.next = curr
                evenCurr = evenCurr.next
            else:
                oddCurr.next = curr
                oddCurr = oddCurr.next
            counter += 1
            temp = curr.next
            curr.next = None
            curr = temp
        oddCurr.next = evenDummyHead.next
        return oddDummyHead.next