# CSPT19 Lecture
## [Delete Node in a Linked List](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)
    output: 1-->3
    
    1-->2-->3 remove Node(1)
    2-->3
    
    Plan
    Change the current node's value to the next node's value
    Remove the tail node
    """
    """
    1-->2-->4-->5-->None
    """
    def deleteNode(self, node):
        curr = node
        curr.val = curr.next.val
        curr.next = curr.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: None
    output: None
    
    input: 3-->6-->9-->8
    output: 8-->9-->6-->3
    
    input: 1
    output: 1
    
    Plan
    Use three pointers: prev, curr, temp
    temp is to not lose track of the next node to reverse
    curr is the node that we're currently reversing
    prev is the previous node of curr
    """
    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:
    """
    input: 5->6->8->10
    output: 5->8->6->10
    
    oddNodes (*)->5->8->6->10
    evenNodes (*)
    """
    def oddEvenList(self, head: ListNode) -> ListNode:
        if head == None:
            return None
        
        oddDummyHead = ListNode('*')
        oddCurr = oddDummyHead
        
        evenDummyHead = ListNode('*')
        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