# CSPT13 Build Week 3
## [Odd Even Linked List](https://leetcode.com/problems/odd-even-linked-list)

"""
Understand:
Empty list

Odd number list
Input: 1->2->3
Output: 1->3->2

Even number list
Input: 1->2->3->4
Output: 1->3->2->4

Plan:
Use dummy-head to create two lists with even and odd elements
Append even list to end of odd list
"""

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    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

## [Remove Nth Node](https://leetcode.com/problems/remove-nth-node-from-end-of-list)

"""
Understand:
Input: 1->2->3, n = 1
1->2

Input: 1->2->3, n = 2
1->3

Input: 1->2->3, n = 3
2->3

Plan:
Use dummy head + two-pointer technique to remove the nth node

You can also traverse the list twice to get the length so you know which node to remove
"""

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

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        if head == None:
            return None
        dummyHead = ListNode(-1)
        dummyHead.next = head
        left = right = dummyHead
        for i in range(n):
            right = right.next
        while right.next != None:
            left = left.next
            right = right.next
        left.next = left.next.next
        return dummyHead.next