Interview Cake's Linked Lists

Delete node, Linked list has a cycle, Reverse a linked list, Kth to last node

1. Delete a node from a singly-linked list, given only a pointer to that node.

Approach:

- Since we don't have access to the previous node, simply copy the value and
  pointer of the next node and copy them into the current node.

Cost:

- O(1) time and O(1) space.

Link to solution →

2. Determine if a singly-linked list has a cycle.

Approach:

- Keep two pointers starting at the first node such that: every time one moves
  one node ahead, the other moves 2 nodes ahead.
- If the linked list has a cycle, the faster one will catch up with the slow
  one. Otherwise, the faster one will each the end.

Cost:

- O(n) time and O(1) space.

Link to solution →

3. Reverse a linked list in-place.

Approach:

- Iterate through the list and point each node's next pointer to the previous item.

Cost:

- O(n) time, O(1) space.

Link to solution →

4. Find the kth to last node in a linked list.

Example:

- Input: list = 1 -> 2 -> 3 -> 4 -> 5 -> 6, k = 2
  Output: 5, because 5 is the 2nd to the last node (6)

Approach:

- Use two pointers such that one starts at the beginning and the other one
  starts at k distance apart.
- Walk both at the same speed toward the end.
- When one hits the tail, the other one is on the target node.

Cost:

- O(n) time, O(1) space.

Link to solution →

For more coding problems, please visit https://github.com/hoanhan101/algo.

If you’re interested in getting updates for such content like these, consider joining my mailing list here →


Tagged: #interviewcake, #algorithm