How to find middle element of linked list in one pass?
LinkedList data structure contains a collection of the node and has head and tail. To find the middle element in one pass we can use two-pointer approach.
Algorithm:
1). Create two pointers 'slow' and 'fast'.
2). Start iterating the list, in each iteration increment 'fast' by 1 and on alternate iteration increment 'slow' by 1.
3). When the 'fast' pointer reaches the end, the 'slow' pointer will point to a middle element of the linked list.
-K Himaanshu Shuklaa..
LinkedList data structure contains a collection of the node and has head and tail. To find the middle element in one pass we can use two-pointer approach.
Algorithm:
1). Create two pointers 'slow' and 'fast'.
2). Start iterating the list, in each iteration increment 'fast' by 1 and on alternate iteration increment 'slow' by 1.
3). When the 'fast' pointer reaches the end, the 'slow' pointer will point to a middle element of the linked list.
How to find the kth element from the end in a linked list in one pass?
This question is exactly similar to find middle element of linked list in a single pass.
We need to apply the same trick and maintain two-pointers. Increment another pointer, when first has moved up to the kth element, then when the first pointer reaches the end of the linked list, the second pointer will be pointing to the kth element from last in a linked list.
How to find if a linked list has a loop or cycle?
In Linkedlist each node contains two parts data and address, where address part points to another node in a linked list. The last node (tail) of a linked list points to null. If a linked list contains a loop or cycles it is known as a circular or cyclic linked list.
To check if the given list has a loop, we will use a two-pointer approach.
We will maintain fast and slow pointer. In each iteration fast pointer moves two nodes, while the slow pointer moves to one node. When the list has a loop or cycle, than both fast and slow pointer will meet at some point during iteration.
If they don't meet and fast or slow point to null, then the linked list is not cyclic.
This question is exactly similar to find middle element of linked list in a single pass.
We need to apply the same trick and maintain two-pointers. Increment another pointer, when first has moved up to the kth element, then when the first pointer reaches the end of the linked list, the second pointer will be pointing to the kth element from last in a linked list.
How to find if a linked list has a loop or cycle?
In Linkedlist each node contains two parts data and address, where address part points to another node in a linked list. The last node (tail) of a linked list points to null. If a linked list contains a loop or cycles it is known as a circular or cyclic linked list.
To check if the given list has a loop, we will use a two-pointer approach.
We will maintain fast and slow pointer. In each iteration fast pointer moves two nodes, while the slow pointer moves to one node. When the list has a loop or cycle, than both fast and slow pointer will meet at some point during iteration.
If they don't meet and fast or slow point to null, then the linked list is not cyclic.
-K Himaanshu Shuklaa..
No comments:
Post a Comment