Linked List

Question 1

206. Reverse Linked List (Easy)

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

Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Answer 1

Iterate through the list and reverse the links between each node.

Create 3 variables, current (which starts off at head), and the pointers prev and next (which are both null to start).

Current is the node you’re currently on. Any time you adjust prev and next, you’re adjusting the pointers.

Do 4 things with each node…

1. Set next to current.next (aka move the pointer forward).
2. Set current.next to prev (for the first iteration, this means the head node of ‘1’ now points to null instead of 2)
3. Update prev to current (move the slider forward so prev now points at ‘1’)
4. Update current to next (change the node to 2.)

Finally, assign head to prev to change the head and return head.

Question 2

21. Merge Two Sorted Lists (Easy)

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

Merge the two lists into 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.

Example 1
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:
Input: list1 = [], list2 = []
Output: []

Answer 2

Use a dummy node to keep track of the previous value (we need this because there is no previous value at first).
Assign a variable prev to dummy (this is what will keep track of the list).

Check to see if l1 > l2.

Use a while looping checking to see if l1 and l2 still have values and…

1. check to see is l1 is greater than l2.
2. If it is, set prev.next to l1. (If it isn’t do steps 2, 3, and 4 for l2.
3. Move prev pointer forward to l1.
4. Move l1 forward to l1.next.

Then, when one list has run out, connect prev (the last value to be added to the merged list), to the remaining list.

if (!l1) prev.next = l2
if (!l2) prev.next = l1

Finally, return dummy.next, which holds a record of the head of the list.

Question 3

141. Linked List Cycle (Easy)

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.

Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Answer 3

Floyd’s cycle finding algorithm aka the tortoise and the hare approach,

have two pointers going at different speeds. If there’s a cycle, eventually they will land on the same node

1. while loop checking for fast && fast.next
2. move the pointers up 1 and 2 (slow.next, fast.next.next)
3. if slow===fast return true. otherwise while loop ends and return false