-
Notifications
You must be signed in to change notification settings - Fork 13
Chapter 2
2.1 Remove Dups: Write code to remove duplicates from an unsorted linked list. FOLLOW UP How would you solve this problem if a temporary buffer is not allowed?
2.2 Return Kth to Last: Implement an algorithm to find the kth to last element of a singly linked list.
2.3 Delete Middle Node: Implement an algorithm to delete a node in the middle of a singly linked list, given only access to that node.
EXAMPLE
Input: the node c from the linked list a->b->c->d->e
Result: nothing is returned, but the new linked list looks like a->b->d->e
2.4 Partition: Write code to parition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x.
2.5 Sum Lists: You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
EXAMPLE
Input: (7 -> 1 -> 6) + (5 -> 9 -> 2). that is, 617 + 295.
Output: 2 -> 1 -> 9. That is, 912.
FOLLOW UP
Suppose the digits are stored in forward order. Repeat the above problem.
EXAMPLE
Input: (6 -> 1 -> 7) + (2 -> 9 -> 5). That is 617 + 295.
Output: 9 -> 1 -> 2. That is, 912.
2.6 Palindrome: Implement a funciton to check if a linked lits is a palindrome.
2.7 Intersection: Given two (singly) linked lists, determine if the two lists intersect. Return th eintersection node. Node that the intersection is defined based on reference, not value. That is if the kth node of the first linked list is exactly the same node (by reference) as the jth node of the second linked list, then they are intersecting.
2.8 Loop Detection: Given a circular linked list, implement an algorithm that returns the node at the beginning of the loop.
DEFINITION
Circular linked list: A (corrupt) linked list in which a node's next pointer points to an earlier node, so as to make a loop in the linked list.
EXAMPLE
Input: A -> B -> C -> D -> E -> C [the same C as earlier]
Output: C