Teaching Kids Programming: Videos on Data Structures and Algorithms
Given a head of the linked list, how do we efficiently get the middle of the linked list? Sure we can follow the linked list once and count the number of the nodes. Once we reach the end, we know the middle of linked list immediately by halvening the total number of nodes. This time complexity is O(N) and we need to traverse the linked list 1.5 times.
We can do better in O(N) time and only traverse the linked list exactly once. We can use two pointers: fast and slow. The fast pointer traverse two steps at a time, and the slow pointer traverses one step at a time. When the fast pointer reaches the end, the slow pointer points to the middle node.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | class Node: def __init__(self, val, nextNode = None): self.val = val self.nextNode = nextNode def addNode(self, val): newNode = Node(val) self.nextNode = newNode return newNode head = Node(1) p = head for i in range(2, 10): p = p.addNode(i) # get the middle of the linked list def mid(head): fast, slow = head, head while fast is not None and fast.nextNode is not None: fast = fast.nextNode.nextNode slow = slow.nextNode return slow m = mid(head) print(m.val) # middle node is 5 |
class Node: def __init__(self, val, nextNode = None): self.val = val self.nextNode = nextNode def addNode(self, val): newNode = Node(val) self.nextNode = newNode return newNode head = Node(1) p = head for i in range(2, 10): p = p.addNode(i) # get the middle of the linked list def mid(head): fast, slow = head, head while fast is not None and fast.nextNode is not None: fast = fast.nextNode.nextNode slow = slow.nextNode return slow m = mid(head) print(m.val) # middle node is 5
See other implementations of getting the middle of the linked list:
- Fast and Slow Pointer to Get the Middle of the Linked List
- Teaching Kids Programming – Fast and Slow Pointer to Obtain the Middle of the Linked List
- How to Compute the Middle of the Linked List using Fast and Slow Pointer?
- GoLang: Compute the Middle of a Linked List
–EOF (The Ultimate Computing & Technology Blog)
loading...
Last Post: Algorithm to Determine if String Halves Are Alike (Same Number of Vowels)
Next Post: Algorithm to Find the Longest Alliteration
