Sandbox

Problem Solution # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: # jump is always at the tail of the previous group # When reversing is complete in the next group, # jump.next points to that group's head # and jump mov..

Problem Solution # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: if not head: return head # need to know "k % length of list" to find the point of rotation # go to the end of the list while counting length lptr = head l ..

Problem Solution # 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: Optional[ListNode]) -> Optional[ListNode]: odd = dummy = ListNode(0) even = dummy2 = ListNode(0) # group odds and evens, and put the evens after odds while head: odd.next = head even.next = head.next odd = ..

Problem Solution # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]: if not head or not head.next: return head # find the middle of the linked list # https://leetcode.com/problems/middle-of-the-linked-list/ slow = head fast = head.next..

Problem Solution # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: dummy = curr = ListNode(0) # always insert into curr.next while list1 and list2: # add list1 nodes until we find one that is larger t..

Problem Solution Same method as the Remove Nth Node From End of List , except we have a third pointer that points to the Nth value from the start of the list. Time Complexity O(N) Space Complexity O(1)

Problem Solution Need to find a way to both reach the end of the list with one pointer (so that we can find the n'th node from the end) and also the n'th node from the end simultaneously with a second pointer. Fast pointer will have a head start by n nodes. This will cause slow pointer to reach the n'th node from the end at the same time that fast pointer reaches the end. Actually, slow pointer ..

Problem Solution If one list is longer than the other, ignore the leading part and start at the point where the total number of nodes will be the same. Compare one by one, and if none of the nodes are equivalent, return null. # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def getIntersectionNode(self, headA: ListN..

Problem Solution # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]: if not head or not head.next: return head curr = head n = head.next while True: if curr.val != n.val: curr.next = n curr = curr.next n = n.next if not n: curr..

Problem Solution Iterative: # Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object): def reverseList(self, head): """ :type head: ListNode :rtype: ListNode """ prev = None curr = head while curr is not None: nextNode = curr.next curr.next = prev prev = curr curr = nextNode return prev Recurs..