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: Compare one by one
Time Complexity: O(kN) 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(1) It's not hard to apply in-place method - connect selected nodes instead of creating new nodes to fill the new linked list.
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).