CP2: Topic 5: Linked Lists and Data Structures

Competitive Programming II (Spring 2020)

​

Dhruv Ramanujan

Example Problems

• LeetCode: Intersection of Two Linked Lists
• Merge Two Sorted Lists In Place
• LeetCode: Add Two Numbers II
• LeetCode: Linked List Cycle II

Homework Problems

• Coconut Splat
• Grandpa Bernie
• Join Strings

LeetCode: Intersection of Two Linked Lists

LeetCode: Intersection of Two Linked Lists

• Problem: Given two linked lists that intersect, return the intersection node.
• Time Complexity: O(n)
• Space Complexity: O(1)

LeetCode: Intersection of Two Linked Lists

• Pointer A points to a1
• Pointer B points to b1
• When either pointer reaches the end of the list, move it to the head of the other list

LeetCode: Intersection of Two Linked Lists

• Why does this work?
• Pointer A traverses: a nodes, b nodes, c nodes
• Pointer B traverses: a nodes, b nodes, c nodes
• Since the set of traversed nodes is the same length they intersect at the same time.

LeetCode: Merge Two Sorted Lists In Place

LeetCode: Merge Two Sorted Lists In Place

• Problem: Given two sorted linked lists merge them together by only changing next pointers. Use as few changes as possible.
• Time Complexity: O(n)
• Space Complexity: O(1) extra space

LeetCode: Merge Two Sorted Lists In Place

• Have a pointer at the start of each list
• Increment only 1 pointer at a time, starting with the smaller one.
• When the moving pointer has a larger value than the stationary pointer:
• Change the links on the list
• Start moving the other pointer

LeetCode: Merge Two Sorted Lists In Place

• Have a pointer at the start of each list
• Increment only 1 pointer at a time, starting with the smaller one.
• When the moving pointer has a larger value than the stationary pointer:
• Change the links on the list
• Start moving the other pointer

LeetCode: Add Two Numbers II

LeetCode: Add Two Numbers II

• Problem: Given 2 linked lists representing 2 integers, add them together into a new linked list.
• Time Complexity: O(n)
• Space Complexity: O(n) extra space

LeetCode: Add Two Numbers II

• Use 2 stacks A, B to store values while traversing the linked list.
• Pop Values from the stacks and add them.
• Store an extra variable for carry bits.
• Add extra node if there is a carry bit at the end!

LeetCode: Add Two Numbers II

• Use 2 stacks A, B to store values while traversing the linked list.
• Pop Values from the stacks and add them.
• Store an extra variable for carry bits.
• Add extra node if there is a carry bit at the end!

LeetCode: Linked List Cycle II

LeetCode: Linked List Cycle II

• Problem: Given a Linked List (with a pointer to the head), return the node where the cycle begins.
• Time Complexity: O(n)
• Space Complexity: O(1)

LeetCode: Linked List Cycle II

• Step 1: Detect a cycle
• Fast Pointer moves 2 steps at a time
• Slow Pointer moves 1 step at a time
• If they meet, there is a cycle

LeetCode: Linked List Cycle II

• Step 2: Find Starting Point
• L1 = distance from head to start of loop
• L2 = distance from start of loop to meeting point
• N = number of loops
• C = Length of loop

Slow Pointer: L1 + L2

Fast Pointer: L1 + L2 + NC

• 2(L1+L2) = L1+L2+NC
• L1+L2 = NC
• L1 = NC - L2
• L1 = (N-1)C + (C-L2)
• L1 = [N-1 Loops of C]+ [The distance from the meeting point to the start of the loop]

LeetCode: Linked List Cycle II

• Step 2: Find Starting Point
• Create a new pointer “head”
• Slow increments by 1 node
• Head increments by 1 node
• The meeting point is the start of the cycle
• L1 = 1, Meeting->Start = 1

• L1 = [N-1 Loops of C]+ [The distance from the meeting point to the start of the loop]

Homework Hints

Homework Hints: Coconut Splat

• Run this like a simulation.

​

• Use a list of tuples (players, hand status) to store information
• Ex: [ (1, “Hands Folded”), (2, “Fist”), (2, “Fist), (3, “Palm Down”) ]

​

• When a hand goes behind the back, remove it from the list

​

• If the list contains 1 remaining element, they are the winner

Homework Hints: Grandpa Bernie

• Use an map of arrays (country: [dates]) to store information
• map[“US”] = [1960, 2000]
• map[“Iceland”]-->[2000]
• map[“Greenland”]-->[2016, 2018]

​

• Make sure the date lists are stored in sorted order

​

• It might help to insert in arbitrary order and sort after all insertions. O(nlogn)

Homework Hints: Join Strings

• Do not keep appending strings.

​

• Use a Linked List with the string as the value stored.

​

• Node Data Structure:
• Value: The string to store
• Next: Next node it is connected to
• End: The node at the end of the string of connections (useful for concatenating string of nodes)

​

• Only the head nodes need to hold information for the end variable.