Linked List

Question 1

Given the head of a singly linked list, reverse the list, and return the reversed list.

Answer 1

• Track previous node and current node.
• Use temporary next variable when you swap values.
• Return PREVIOUS

VERY COMMON INTERVIEW QUESTION!

Question 2

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Answer 2

O(min(n, m)) (whichever list is shorter)

cur1 and cur2 as your 2 lists
tail as the new list you’re constructing.
while cur1 AND cur2:
Keep counter: if it’s even, add cur2, if it’s odd add cur1

After the loop, tack on whichever list still have nodes remaining

Question 3

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Answer 3

• Visited set to track which nodes have been visited.
• Add the node itself, not the val, because val can be repeated.

O(n)

Question 4

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Answer 4

• Add a dummy node at the beginning, in case the head is the one that is removed.
• Use two pointers spaced n apart and move these together through the Linked List.

Question 5

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

Answer 5

• You can do this with a stack, but you can also do it with O(n) space complexity.
• Use fast and slow pointer to find the mid point of the list. Midpoint is slow + 1
• Reverse the second half of the list.
• Swap by traversing the two halves.
• Remember to set cur = None when you reach the end of the swapping.

Question 6

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Answer 6

You can use merge sort.
- Go through the list of LinkedLists in pairs. Merge each pair using “Merge Sorted List” (LC easy algorithm).
- Keep merging the lists until you have just 1 list.