Problem on loops
Pointers
Lists
Conclusion
Loops, Pointers and Linked Lists
Abhilash I
abhilashi@students.iiit.ac.in
October 20, 2008
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Pointers
Lists
Conclusion
Table of contents
1 Problem on loops
Solution
2 Pointers
Problem 1
Problem 2
Never forget these
3 Lists
Decleration
Operations
Problems
4 Conclusion
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Pointers
Solution
Lists
Conclusion
Problem on loops
for(i=0; i<n;i++)
for(i=0;i<p;i++)
printf("yes");
Problem statement
On executing the above code how many times will yes be printed
for different values of p=n, n-1, n-2;
value of p answer
n ?
n-1 ?
n-2 ?
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Pointers
Solution
Lists
Conclusion
Solution
value of p answer
n n
n-1 ∞ n-1
n-2 ∞
for(i=0; i<n;i++) while(i<n){
for(i=0;i<p;i++) i=0;
printf("yes"); while(i<p){ i++; }
i++;
}
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Pointers
Solution
Lists
Conclusion
Solution
value of p answer
n n
n-1 ∞ n-1
n-2 ∞
for(i=0; i<n;i++) while(i<n){
for(i=0;i<p;i++) i=0;
printf("yes"); while(i<p){ i++; }
i++;
}
Moral of the story
Tricky problems look simple.
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Problem 1
Pointers
Problem 2
Lists
Never forget these
Conclusion
Problem1
void func(char *x){
*x=’b’;
}
main(){
char ch=’a’;
char *a=&ch;
char *b=a;
func(a);
printf("%c %c\n", *a, *b);
}
Question
What is the output of the above program ?
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Problem 1
Pointers
Problem 2
Lists
Never forget these
Conclusion
Problem 2
char *func(char *x){
x=malloc(100);
strcpy(x, "low");
return x;
}
main(){
char *x="high",*y="high";
func(x);
y=func(y);
printf("%s %s\n", x, y);
}
Question
What is the output of the above program ?
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Problem 1
Pointers
Problem 2
Lists
Never forget these
Conclusion
Never forget these
Pointer is a variable.
In the decleration char *p; What is the data type of p and *p ?
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Problem 1
Pointers
Problem 2
Lists
Never forget these
Conclusion
Never forget these
ANSI C standard defines string literals to be constant.
char *p="tutorial";
p[0]=’z’; //results in a segmentation fault
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Problem 1
Pointers
Problem 2
Lists
Never forget these
Conclusion
Never forget these
You cannot modify the base address of an array.
char buff[100];
char *p="pointer"
buff=p; //raises a compilation error;
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Problem 1
Pointers
Problem 2
Lists
Never forget these
Conclusion
Never forget these
Pointer is a variable.
In the decleration char *p; What is the data type of p and *p ?
ANSI C standard defines string literals to be constant.
char *p="tutorial";
p[0]=’z’; //results in a segmentation fault
You cannot modify the base address of an array.
char buff[100];
char *p="pointer"
buff=p; //raises a compilation error;
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Decleration
Pointers
Operations
Lists
Problems
Conclusion
Basics: Decleration
In C
struct node{
int data;
struct node * next;
}
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Decleration
Pointers
Operations
Lists
Problems
Conclusion
Basics: Decleration
In C++
struct node{
int data;
node * next;
}
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Decleration
Pointers
Operations
Lists
Problems
Conclusion
Basics: Decleration
In C
struct node{
int data;
struct node * next;
}
In C++
struct node{
int data;
node * next;
}
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Decleration
Pointers
Operations
Lists
Problems
Conclusion
Basics: Operations
Allocation of Memory
struct node *nn = (struct node *)malloc(sizeof(struct node))); //c
node *nn = new node; //c++ style
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Decleration
Pointers
Operations
Lists
Problems
Conclusion
Basics: Operations
Allocation of Memory
struct node *nn = (struct node *)malloc(sizeof(struct node))); //c
node *nn = new node; //c++ style
Insertion
Deletion
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Decleration
Pointers
Operations
Lists
Problems
Conclusion
Nature of problems
For most of the questions naive solutions are trivial
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Decleration
Pointers
Operations
Lists
Problems
Conclusion
Nature of problems
For most of the questions naive solutions are trivial
Yes, interviewers look for optimized versions
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Decleration
Pointers
Operations
Lists
Problems
Conclusion
Nature of problems
For most of the questions naive solutions are trivial
Yes, interviewers look for optimized versions
We will walk through a set of examples in the next few slides
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Decleration
Pointers
Operations
Lists
Problems
Conclusion
Problem Statement
Find the maximum/mininum elements of a linked list ?
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Decleration
Pointers
Operations
Lists
Problems
Conclusion
Problem Statement
Find the maximum/mininum elements of a linked list ?
node* findMaximum(node *head){
node * returnValue=head;
while(head!=NULL){
if (head->data > returnValue->data){
returnValue=head;
}
head=head->next;
}
return returnValue;
}
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Decleration
Pointers
Operations
Lists
Problems
Conclusion
Problem Statement
Find union/intersection of two linked lists ?
Typically you would have to write a function that returns a
new list
Please write it down.
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Decleration
Pointers
Operations
Lists
Problems
Conclusion
Problem Statement
Reverse a linked list.
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Decleration
Pointers
Operations
Lists
Problems
Conclusion
Problem Statement
Reverse a linked list.
Constraints
O(1) space complexity
O(N) time complexity
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Decleration
Pointers
Operations
Lists
Problems
Conclusion
Problem Statement
Reverse a linked list.
Constraints
O(1) space complexity
O(N) time complexity
Hottest problem: probably the most asked question
Iterative solution
Recursive solution
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Decleration
Pointers
Operations
Lists
Problems
Conclusion
Iterative solution
void reverse(struct node **x){
struct node *q,*r,*temp;
r=*x;
q=NULL;
while(r!=NULL){
temp=q;
q=r;
r=r->next;
q->next=temp;
}
*x=p;
}
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Decleration
Pointers
Operations
Lists
Problems
Conclusion
Recursive solution
node* reverse(node** head , node* cur){
if(cur->next == NULL) {
*head = cur;
}
else{
(reverse(head,cur->next))->next = cur;
cur->next = NULL;
}
return cur;
}
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Decleration
Pointers
Operations
Lists
Problems
Conclusion
Not so easy deletion
Problem Statement
Given a pointer to a node in a linked list, how do you delete that
particular node ?
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Decleration
Pointers
Operations
Lists
Problems
Conclusion
Moving two pointers cleverly
Depends on the problem at hand
Example: Move one pointer slowly
like a tortoise and other one fastly
like a hare
Next 4 problems based on this
trick
Also known as Floyd’s cycle
detection algorithm
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Decleration
Pointers
Operations
Lists
Problems
Conclusion
k th element from end
Problem Statement
Find the k th element from the end of a linked list ?
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Decleration
Pointers
Operations
Lists
Problems
Conclusion
k th element from end
Problem Statement
Find the k th element from the end of a linked list ?
Constraints
Without using integer variable to store length of list.
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Decleration
Pointers
Operations
Lists
Problems
Conclusion
Center of the Linked List
Problem Statement
Find the center of the linked list ?
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Decleration
Pointers
Operations
Lists
Problems
Conclusion
Center of the Linked List
Problem Statement
Find the center of the linked list ?
Constraints
You cannot use integer variables in your solution.
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Decleration
Pointers
Operations
Lists
Problems
Conclusion
Y-shaped Linked List
Problem Statement
Given pointers to two singly-linked lists, find out if they are joined
and also at which node they are joined.
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Decleration
Pointers
Operations
Lists
Problems
Conclusion
Cycle in the Linked List
Problem Statement
Find whether the linked list has a cycle or not ?
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Decleration
Pointers
Operations
Lists
Problems
Conclusion
Cycle in the Linked List
Problem Statement
Find whether the linked list has a cycle or not ?
Solution strategies
By storing the addresses of the elements already seen ?
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Decleration
Pointers
Operations
Lists
Problems
Conclusion
Cycle in the Linked List
Problem Statement
Find whether the linked list has a cycle or not ?
Solution strategies
By storing the addresses of the elements already seen ?
By destructing the linked list ?
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Decleration
Pointers
Operations
Lists
Problems
Conclusion
Cycle in the Linked List
Problem Statement
Find whether the linked list has a cycle or not ?
Solution strategies
By storing the addresses of the elements already seen ?
By destructing the linked list ?
By reversing the linked list ?
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Decleration
Pointers
Operations
Lists
Problems
Conclusion
Cycle in the Linked List
Problem Statement
Find whether the linked list has a cycle or not ?
Solution strategies
By storing the addresses of the elements already seen ?
By destructing the linked list ?
By reversing the linked list ?
By cleverly moving two pointers
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
Problem on loops
Pointers
Lists
Conclusion
Conclusion
Talked about a simple problem on loops
Facts we shouldn’t forget about about pointers.
Problems on linked list
Moving pointers cleverly to solve problems.
Please drop your comments : abhilashi@students.iiit.ac.in
Abhilash I abhilashi@students.iiit.ac.in Loops, Pointers and Linked Lists
