# CSPT27 Lecture 9

## Sandbox

class LinkedListNode:
    def __init__(self, value):
        self.value = value
        self.next = None
    def __repr__(self):
        description = ""
        curr = self
        while curr != None:
            description += f"-->{curr.value}"
            curr = curr.next
        return description

a = LinkedListNode("1")
b = LinkedListNode("2")
c = LinkedListNode("3")
d = LinkedListNode("4")
a.next = b
b.next = c
c.next = d

def insertBeforeNode(nodeToInsert, otherNode):
    nodeToInsert.next = otherNode
    
d = LinkedListNode(5)
insertBeforeNode(d, a)

## Delete Node in a Linked List

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

class Solution:
    """
    Understand
    input: 1*-->2
    output: 2
    
    input: 1-->2*-->3
    output: 1-->3
    
    Plan
    Change the given node's value, to be the next node's value
    And remove the next node from the list by changing the next pointer
    """
    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:
    """
    Understand
    input: 1
    output: 1
    
    input: 1-->2
    output: 2-->1
    
    input: 1-->2-->3
    output: 3-->2-->1
    
    Plan
    Use multiple pointers to reverse the list one node at a time
    
    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 Linked-List

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    """
    Understand
    A->B->C->D->E
    A->C->E->B->D
    
    A->B
    A->B
    
    A->A*->B
    A->B->A*
    
    Plan
    Create two dummy lists: one for even, one for odd.
    Walk through the original list and put the node in the correct list.
    Combine both lists together and return the head of the odd list.
    
    Runtime: O(n)
    Space: O(1)
    """
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        oddDummyHead = ListNode('*')
        oddCurr = oddDummyHead
        evenDummyHead = ListNode('*')
        evenCurr = evenDummyHead
        position = 1
        curr = head
        while curr != None:
            if position % 2 == 0:
                evenCurr.next = curr
                evenCurr = evenCurr.next
            else:
                oddCurr.next = curr
                oddCurr = oddCurr.next
            position += 1
            temp = curr.next
            curr.next = None
            curr = temp
        oddCurr.next = evenDummyHead.next
        return oddDummyHead.next