Linked List
Middle of a linked list
[Easy] No.876 Middle of Linked List
Approach: Fast and Slow Pointer
Time Complexity: O(N), where N is the number of nodes in the given list.
Space Complexity: O(1), the space used by slow and fast
Reverese a linked list
[Easy] No.206 Reverese Linked List
Approach: Iterative
Time Complexity: O(N), where N is the number of nodes in the given list.
Space Complexity: O(1)
[Medium] No.92 Reverse Linked List from index m to index n
Approach: Iterative
Time Complexity: O(N), We process each of the nodes at most once (we don't process the nodes after the nth node from the beginning).
Space Complexity: O(1) since we simply adjust some pointers in the original linked list and only use O(1) additional memory for achieving the final result.
Merge two sorted linked list
[Easy] No.21. Merge Two Sorted Lists
Approach: Iterative
Time Complexity: O(n+m), n is the length of l1 and m is the length of l2.
Space Complexity: O(1) The iterative approach only allocates a few pointers, so it has a constant overall memory footprint.
[Hard] No.23. Merge k Sorted Lists
Approach 1: Merge lists one by one
Time Complexity: O(kN) where k is the number of linked lists. We can merge two sorted linked list in O(N) time where N is the total number of nodes in two lists.
Space Complexity: O(1). We can merge two sorted linked list in O(1)O(1) space.
Approach 2: Optimize Approach 1 by Priority Queue
Time Complexity: O(Nlogk) where k is the number of linked lists. N is the number of nodes in the final linked list.
Space Complexity: O(n) Creating a new linked list costs O(n) space. O(k)The code above present applies in-place method which cost O(1) space. And the priority queue (often implemented with heaps) costs O(k)O(k) space (it's far less than NN in most situations).
Floyd's Tortoise and Hare (Cycle Detection)
[Medium] No.142 Linked List Cycle II
![](images/first_intersection.png)
(The above image is from leetcode.com.)
step1. find the intersection points
step2. find the beginning of the cycle
use in linked list questions
use in vector, string questions