Linked Lists

Question 1

206. Reverse Linked List

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

Answer 1

1. instantiate variable to keep track of prev value with value of None. This is because the next node of the last value in a linked list is None
2. instantiate variable to hold the current linked list. we need a variable because we will be reassigning this variable
3. while curr
4. create temporary variable to hold the curr.next node becuase we will be re-assigning this value
5. assign curr.next to be the prev variable
6. assign current list node as prev
7. assign temp next variable (the former forward node) to be curr
8. return prev, as it will be the first node of the newly reversed linked list

Question 2

141. Linked List Cycle

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 2

1. first check to make sure head and head.next exist. if not, return False, because there is not a cycle as it does not have a next value
2. instantiate a slow and fast variable. slow can be head, fast can be head.next
3. while slow exists, fast exists, and fast.next exists:
4. if slow is equal to fast, we know that they are the same listNode which can only happen if there is a cycle so return True.
5. otherwise, set slow index to the next list node and the fast index to the next next node.
6. if the while condition fails, which means that a value of None has been reached. which in turn indicates that the linked list has reached the end, return False because there cannot be a cycle if the linked list has reached the end.

Question 3

21. Merge Two Sorted Lists

Answer 3

https://leetcode.com/problems/merge-two-sorted-lists/

Question 4

19. Remove Nth Node From End of List

Answer 4

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

Question 5

143. Reorder List

Answer 5

https://leetcode.com/problems/reorder-list/