Question:
Order the list with ‘0’ first and ‘1’ second, which has ‘0’ and ‘1’ stored in irregular fashion.
Constraints:
-> Time & Space complexity to be minimal
Example:
Array: 0-1-0-1-1-0-1
Answer: 0-0-0-1-1-1-1
Answer:
-> Start with one pointer from start and another pointer from back.
-> Stop if you find ‘1’ for first pointer
-> Stop if you find ‘0’ for second pointer
-> Interchange till both the pointers are not crossed over.
Complexity:
Time: O(2N) -> O(N) , where N represents longest link list length
Example:
Array: 0-1-0-1
Answer: 0-0-1-1
Tracing:
Step 1:
-> Let Pointer 1 points to head of array
-> Let Pointer 2 points to tail of array
Step 2:
-> Pointer 1 will stop at node 2 as it has '1'
Step 3:
-> Pointer 2 will stop at node 3 as it has '0'
Step 4:
-> Interchange the values of node 2 & 3 with 0 & 1 respectively
Step 5:
-> Pointer 1 crosses over Pointer 2. Stop
Answer:
0-0-1-1
Showing posts with label Link List. Show all posts
Showing posts with label Link List. Show all posts
Monday, December 7, 2009
Saturday, December 5, 2009
Reach i-th position from tail of link list
Question:
To reach i-th position from tail of link-list by traversing only once.
Example:
1-2-3-4-5-6-7-8-9
To reach 3rd node from tail. i.e Node 7
Answer:
-> Take two pointers.
-> Take first pointer to i-th position from head
-> Start incrementing both the pointers
-> When the first pointer reaches the tail, at that point second pointer will be pointing to i-th node from tail
Example:
1-2-3-4-5-6-7-8-9, to reach 3rd node from tail i.e. Node 7.
Tracing:
Step 1:
-> Pointer 1 & Pointer 2 points to node 1
Step 2:
-> Increment Pointer 1 '3' times, as we want 3rd node from tail
Step 3:
-> Increment both the pointers
Movement of Pointer 1: 3-4-5-6-7-8-9
Movement of Pointer 2: 1-2-3-4-5-6-7
Step 4:
Stop when Pointer 1 points to 9, at that time the Pointer 2 points to Node 7
Answer:
Node 7
To reach i-th position from tail of link-list by traversing only once.
Example:
1-2-3-4-5-6-7-8-9
To reach 3rd node from tail. i.e Node 7
Answer:
-> Take two pointers.
-> Take first pointer to i-th position from head
-> Start incrementing both the pointers
-> When the first pointer reaches the tail, at that point second pointer will be pointing to i-th node from tail
Example:
1-2-3-4-5-6-7-8-9, to reach 3rd node from tail i.e. Node 7.
Tracing:
Step 1:
-> Pointer 1 & Pointer 2 points to node 1
Step 2:
-> Increment Pointer 1 '3' times, as we want 3rd node from tail
Step 3:
-> Increment both the pointers
Movement of Pointer 1: 3-4-5-6-7-8-9
Movement of Pointer 2: 1-2-3-4-5-6-7
Step 4:
Stop when Pointer 1 points to 9, at that time the Pointer 2 points to Node 7
Answer:
Node 7
Thursday, December 3, 2009
Test whether two link list have common nodes or not?
Question:
To test whether two link list have common nodes or not?
Hints:
-> There may be more then 1 common nodes
-> The length of both the link list might not be same
Constraints:
-> Time & Space complexity to be minimal
Example 1:
List 1: 1-2-3-4-5-6-7
List 2: a-b-c-6-7
Answer: Common nodes from "Node 6"
Example 2:
List 1: 1-2-3-4-5-6-7
List 2: a-b-c-d-e
Answer: No common nodes
Answer:
-> Take two pointers, each pointing to head of each list
-> Take two counter variables for each list to store the length of list
-> Traverse both the list and increment the count on each node traversal
-> Get the length difference by subtracting the counter with higher value to lower one and put to some difference variable
-> Increment the pointer "difference variable" times whose length is greater
-> Increment both the pointers and compare at each iteration, till any node reaches the tail
If they reach tail and both pointers didn't got common value -> No common nodes
Else -> Common nodes from that node
Complexity:
Time: O(2N) -> O(N) , where N represents longest link list length
Space: O(3) -> O(1)
Example 1:
List 1: 1-2-3-4-5-6-7
List 2: a-b-c-6-7
Answer: Common nodes from "Node 6"
Tracing:
See the previous post.
Example 2:
List 1: 1-2-3-4-5-6-7
List 2: a-b-c-d-e
Answer: No common nodes
Tracing:
Step 1:
-> Let Pointer 1 points to head of List 1 and counter is Length 1
-> Let Pointer 2 points to head of List 2 and counter is Length 2
Step 2:
-> The Length 1 value will be: 7
-> The Length 2 value will be: 5
-> Difference variable value will be: 2
Step 3:
-> List 1 length is bigger, hence Pointer 1 will be incremented two time to point to Node 2
Step 4:
Movement of Pointer 1: 3-4-5-6-7
Movement of Pointer 2: a-b-c-d-e
We reached the tail, hence no common node
Answer:
No common nodes
To test whether two link list have common nodes or not?
Hints:
-> There may be more then 1 common nodes
-> The length of both the link list might not be same
Constraints:
-> Time & Space complexity to be minimal
Example 1:
List 1: 1-2-3-4-5-6-7
List 2: a-b-c-6-7
Answer: Common nodes from "Node 6"
Example 2:
List 1: 1-2-3-4-5-6-7
List 2: a-b-c-d-e
Answer: No common nodes
Answer:
-> Take two pointers, each pointing to head of each list
-> Take two counter variables for each list to store the length of list
-> Traverse both the list and increment the count on each node traversal
-> Get the length difference by subtracting the counter with higher value to lower one and put to some difference variable
-> Increment the pointer "difference variable" times whose length is greater
-> Increment both the pointers and compare at each iteration, till any node reaches the tail
If they reach tail and both pointers didn't got common value -> No common nodes
Else -> Common nodes from that node
Complexity:
Time: O(2N) -> O(N) , where N represents longest link list length
Space: O(3) -> O(1)
Example 1:
List 1: 1-2-3-4-5-6-7
List 2: a-b-c-6-7
Answer: Common nodes from "Node 6"
Tracing:
See the previous post.
Example 2:
List 1: 1-2-3-4-5-6-7
List 2: a-b-c-d-e
Answer: No common nodes
Tracing:
Step 1:
-> Let Pointer 1 points to head of List 1 and counter is Length 1
-> Let Pointer 2 points to head of List 2 and counter is Length 2
Step 2:
-> The Length 1 value will be: 7
-> The Length 2 value will be: 5
-> Difference variable value will be: 2
Step 3:
-> List 1 length is bigger, hence Pointer 1 will be incremented two time to point to Node 2
Step 4:
Movement of Pointer 1: 3-4-5-6-7
Movement of Pointer 2: a-b-c-d-e
We reached the tail, hence no common node
Answer:
No common nodes
Tuesday, December 1, 2009
Find common meet point node of two link lists?
Question:
There are two link list, which meet at some node X,find the meet point?
Hints:
-> There may be more then 1 common nodes
-> The length of both the link list might not be same
Constraints:
-> Time & Space complexity to be minimal
Example:
List 1: 1-2-3-4-5-6-7
List 2: a-b-c-6-7
Here "Node 6" is the meet point.
Answer:
-> Take two pointers, each pointing to head of each list
-> Take two counter variables for each list to store the length of list
-> Traverse both the list and increment the count on each node traversal
-> Get the length difference by subtracting the counter with higher value to lower one and put to some difference variable
-> Increment the pointer "difference variable" times whose length is greater
-> Increment both the pointers and compare at each iteration, till any node reaches the tail
-> The point at which both the pointers get same value is the common node meet point
Complexity:
Time: O(2N) -> O(N) , where N represents longest link list length
Space: O(3) -> O(1)
Example:
List 1: 1-2-3-4-5-6-7
List 2: a-b-c-6-7
Here "Node 6" is the meet point.
Tracing:
Step 1:
-> Let Pointer 1 points to head of List 1 and counter is Length 1
-> Let Pointer 2 points to head of List 2 and counter is Length 2
Step 2:
-> The Length 1 value will be: 7
-> The Length 2 value will be: 5
-> Difference variable value will be: 2
Step 3:
-> List 1 length is bigger, hence Pointer 1 will be incremented two time to point to Node 2
Step 4:
Movement of Pointer 1: 3-4-5-6
Movement of Pointer 2: a-b-c-6
Node 6 is the common meet point.
Answer:
Node 6
There are two link list, which meet at some node X,find the meet point?
Hints:
-> There may be more then 1 common nodes
-> The length of both the link list might not be same
Constraints:
-> Time & Space complexity to be minimal
Example:
List 1: 1-2-3-4-5-6-7
List 2: a-b-c-6-7
Here "Node 6" is the meet point.
Answer:
-> Take two pointers, each pointing to head of each list
-> Take two counter variables for each list to store the length of list
-> Traverse both the list and increment the count on each node traversal
-> Get the length difference by subtracting the counter with higher value to lower one and put to some difference variable
-> Increment the pointer "difference variable" times whose length is greater
-> Increment both the pointers and compare at each iteration, till any node reaches the tail
-> The point at which both the pointers get same value is the common node meet point
Complexity:
Time: O(2N) -> O(N) , where N represents longest link list length
Space: O(3) -> O(1)
Example:
List 1: 1-2-3-4-5-6-7
List 2: a-b-c-6-7
Here "Node 6" is the meet point.
Tracing:
Step 1:
-> Let Pointer 1 points to head of List 1 and counter is Length 1
-> Let Pointer 2 points to head of List 2 and counter is Length 2
Step 2:
-> The Length 1 value will be: 7
-> The Length 2 value will be: 5
-> Difference variable value will be: 2
Step 3:
-> List 1 length is bigger, hence Pointer 1 will be incremented two time to point to Node 2
Step 4:
Movement of Pointer 1: 3-4-5-6
Movement of Pointer 2: a-b-c-6
Node 6 is the common meet point.
Answer:
Node 6
Subscribe to:
Posts (Atom)
Disclaimer:
The above post and all the posts in the blog are derived from facts, information, logical interpretation and logical conclusion of printed and internet materials available to me, perceived and produced by 99 gm brain of mine, which by no means always be accurate, consistent and complete.
All the posts are for personal quick reference only.
If any suggestion, correction, misinterpretation, misconception commented, which will be moderated and deleted if required, to avoid unforeseen issues.
If any trademark / copywrite issue is present, do send in a mail and appropriate tag (logo, name, website link) will be attached to the same.
Additional disclaimer will be attached wherever required in the post.
The above post and all the posts in the blog are derived from facts, information, logical interpretation and logical conclusion of printed and internet materials available to me, perceived and produced by 99 gm brain of mine, which by no means always be accurate, consistent and complete.
All the posts are for personal quick reference only.
If any suggestion, correction, misinterpretation, misconception commented, which will be moderated and deleted if required, to avoid unforeseen issues.
If any trademark / copywrite issue is present, do send in a mail and appropriate tag (logo, name, website link) will be attached to the same.
Additional disclaimer will be attached wherever required in the post.