# CSPT23 Lecture 9
## Playground

class LinkedListNode:
    def __init__(self, value):
        self.value = value
        self.next = None
        self.prev = None
    def __repr__(self):
        linkedListStr = ''
        currNode = self
        while currNode != None:
            linkedListStr += f"{str(currNode.value)}->"
            currNode = currNode.next
        return linkedListStr

a = LinkedListNode(1)
b = LinkedListNode(2)
c = LinkedListNode(3)
a.next = b
b.next = c
b.prev = a
c.prev = b

def getElementAtIndex(linkedListNode, index):
    currIndex = 0
    currNode = linkedListNode
    for i in range(index):
        currNode = currNode.next
    return currNode.value

def search(linkedListNode, valueToSearchFor):
    currNode = linkedListNode
    while currNode != None:
        if currNode.value == valueToSearchFor:
            return currNodea
        currNode = currNode.next
    return None

def insert(linkedListNode, valueToInsert):
    temp = linkedListNode.next
    newNodeToInsert = LinkedListNode(valueToInsert)
    linkedListNode.next = newNodeToInsert
    newNodeToInsert.next = temp

def delete(linkedListNode, valueToDelete):
    currNode = linkedListNode
    while currNode.next.value != valueToDelete:
        currNode = currNode.next
        if currNode == None:
            return
    if currNode != None:
        currNode.next = currNode.next.next

insert(b, 4)
insert(b, 4)
print(a)
delete(a, 4)
print(a)

## [Delete Node](https://leetcode.com/problems/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
    1-->2-->3 remove node 2
    1-->3
    
    1-->2-->3 remove node 1
    2-->3
    """
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        node.val = node.next.val
        node.next = node.next.next

## [Reverse Linked List](https://leetcode.com/problems/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
    """
    def reverseList(self, head: ListNode) -> ListNode:
        curr = head
        prev = None
        while curr != None:
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp
        return prev

## [Odd Even Linked List](https://leetcode.com/problems/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:
    """
    Construct 2 dummy nodes, one for even and one for odd
    Insert nodes in the correct list, by keeping track of 
    the current node you're at and what index you're in
    
    Keep pointers that point to the tail of the odd list and even list
    so that you can keep appending easily
    
    Merge two lists in the end
    """
    def oddEvenList(self, head: ListNode) -> ListNode:
        if head == None:
             return None
        oddDummyHead = ListNode(-1)
        oddCurr = oddDummyHead # always points to the tail of the odd list
        evenDummyHead = ListNode(-1)
        evenCurr = evenDummyHead # always points to the tail of the even list
        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