# CSPT17 Lecture 6
## [Delete Node](https://leetcode.com/problems/delete-node-in-a-linked-list)

class Solution:
    """
    Understand
    1 --> 2 delete 1
    2
    
    1-->2-->3 delete 2
    1-->3
    
    1-->2-->3-->4 delete 1
    2-->3-->4
    
    Plan
    Override the value of the node to be deleted to the next node's value
    Do the same thing for the rest of the LL
    Remove the tail at the end
    
    Runtime: O(n) where n = number of nodes
    Space: O(1)
    """
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        curr = node
        while curr != None:
            curr.val = curr.next.val # copy the next node's value
            if curr.next.next == None:
                curr.next = None
            curr = curr.next # go to the next node

## [Reverse LL](https://leetcode.com/problems/reverse-linked-list/)

class Solution:
    """
    Understand
    
    1
    output: 1
    
    1 --> 2
    output: 2-->1
    
    1-->2-->3-->4
    output: 4-->3-->2-->1
    
    Plan
    Use two pointers: prev and curr to reverse the list
    Use temp variable to save the next node to reverse
    return prev at the end
    
    Runtime: O(n)
    Space: O(1)
    """
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        curr = head
        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/)

class Solution:
    """
    1-->2-->3
    output: 1-->3-->2
    
    1-->2-->3-->4
    output:1-->3-->2-->4
    
    1
    output: 1
    
    Plan
    Create two dummy nodes: even and odd
    put all even nodes into even list
    put all odd nodes into odd list
    append lists together
    return oddDummyHead.next
    
    Runtime: O(n)
    Space: O(1)
    """
    def oddEvenList(self, head: ListNode) -> 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