sp-linked-list
https://practice.geeksforgeeks.org/tracks/sp-linked-list/?batchId=152
Problems
Print Linked List elements Solved on: April 20, 2020
void display(Node *head)
{
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}Linked List Insertion Solved on: April 20, 2020
// function inserts the data in front of the list
Node *insertAtBegining(Node *head, int newData) {
struct Node *temp=new Node(newData);
if (head == NULL) {
head = temp;
} else {
temp->next = head;
head = temp;
}
return head;
}
// function appends the data at the end of the list
Node *insertAtEnd(Node *head, int newData) {
struct Node *newNode =new Node(newData);
Node *temp=head;
if (head == NULL) {
head = newNode;
} else {
while (temp->next !=NULL) {
temp=temp->next;
}
temp->next = newNode;
}
return head;
}Delete a Node in Single Linked List Solved on: April 20, 2020
/*You are required to complete below method*/
Node* deleteNode(Node *head,int x)
{
int c=1;
Node *temp1 = head;
if (x==1) {
head = temp1->next;
} else {
while (c<x-1) {
temp1 = temp1->next;
c++;
}
temp1->next = temp1->next->next;
}
return head;
}Count nodes of linked list Solved on: April 20, 2020
// head : reference to head of linked list
int getCount(struct Node* head){
int c=0;
while (head != NULL) {
head = head->next;
c++;
}
return c;
}Node at a given index in linked list Solved on: April 20, 2020
// Should return data of node at given index. The function may
// assume that there are at least index+1 nodes in linked list
int GetNth(struct node* head, int index){
int c=1;
node *temp = head;
while (c!=index) {
temp = temp->next;
c++;
}
return temp->data;
}Finding middle element in a linked list Solved on: April 20, 2020
int getMiddle(Node *head)
{
int c=0,mid=0;
Node *temp=head;
while (temp!=NULL){
temp=temp->next;
c++;
}
mid = int(c/2)+1;
Node *temp1=head;
int i=0;
while (i<mid-1) {
temp1 = temp1->next;
i++;
}
return temp1->data;
}
Reverse a linked list Solved on: 21st April 2020
Node* reverseList(Node *head) {
Node *prev = NULL;
Node *curr = head;
Node *next = NULL;
while (curr != NULL) {
next = curr->next;
curr -> next = prev;
prev = curr;
curr = next;
}
head = prev;
return head;
}
Detect Loop in linked list Solved on: 21st April 2020
int detectloop(Node *head) {
Node *temp1 = head;
Node *temp2 = head;
while (temp1 != NULL && temp2 != NULL && temp2->next != NULL) {
temp1 = temp1->next;
temp2 = temp2->next->next;
if (temp1 == temp2) {
return 1;
}
}
return 0;
}Remove loop in Linked List Solved on: 21st April 2020
void removeTheLoop(Node *head)
{
Node *temp1 = head;
Node *temp2 = head;
while (temp1 && temp2 && temp2->next != NULL) {
temp1 = temp1-> next;
temp2 = temp2->next->next;
if (temp1 == temp2) {
temp1=head;
while(temp1->next != temp2->next)
{
temp1=temp1->next;
temp2=temp2->next;
}
temp2->next=NULL;
}
}
}
Rotate a Linked List Solved on: 21st April 2020
Node* rotate(Node* head, int k) {
Node *temp1 = head;
while (temp1->next) {
temp1= temp1->next;
}
temp1->next = head;
int c=1;
Node *temp2 = head;
while (c<k && temp2->next) {
temp2 = temp2->next;
c++;
}
head = temp2->next;
temp2->next = NULL;
return head;
}
Delete node in Doubly Linked List Solved on: 23rd April 2020
void deleteNode(Node **head_ref, int x)
{
int c=1;
Node *temp = *head_ref;
if (*head_ref == NULL)
return;
// If x is head node
if(x==1){
*head_ref = temp->next;
temp->next->prev = NULL;
return;
}
else {
while (c<x-1 && temp->next) {
temp = temp->next;
c++;
}
Node *temp1 = temp;
// If the x is not a last node
if (temp->next->next){
temp->next = temp->next->next;
temp->next->prev = temp1->next;
} else {
// If x is a last node
temp->next = NULL;
}
}
}Remove duplicates from an unsorted linked list Solved on: April 24th 2020
Node * removeDuplicates( Node *head)
{
Node *temp = head;
Node *temp1 = head;
Node *prev = head;
vector <int> v;
vector<int>::iterator it;
while (temp){
v.push_back(temp->data);
temp = temp->next;
}
// referance https://www.techiedelight.com/remove-duplicates-vector-cpp/
unordered_set<int> s;
auto end = copy_if(v.begin(), v.end(), v.begin(),
[&s](int const &i) {
return s.insert(i).second;
});
v.erase(end, v.end());
for (auto i = v.begin(); i != v.end(); i++) {
temp1->data = *i;
prev = temp1;
temp1 = temp1->next;
}
prev->next = NULL;
return head;
}Merge two sorted linked lists Learnt on: 21st July 2020
Node* sortedMerge(Node* head_A, Node* head_B) {
if (!head_A){
return head_B;
}
if (!head_B){
return head_A;;
}
if (head_A->data < head_B->data) {
head_A->next = sortedMerge(head_A->next, head_B);
return head_A;
}
else {
head_B->next = sortedMerge(head_A, head_B->next);
return head_B;
}
}
SinglyLinkedListNode* mergeLists(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {
SinglyLinkedList *list = new SinglyLinkedList();
SinglyLinkedListNode *temp1 = head1, *temp2 = head2;
while (temp1 != NULL && temp2 != NULL) {
if (temp1->data < temp2->data) {
list->insert_node(temp1->data);
temp1 = temp1->next;
} else {
list->insert_node(temp2->data);
temp2 = temp2->next;
}
}
while (temp1 != NULL) {
list->insert_node(temp1->data);
temp1=temp1->next;
}
while (temp2 != NULL) {
list->insert_node(temp2->data);
temp2=temp2->next;
}
return list->head;
}Intersection Point in Y Shapped Linked Lists Solved on: 21st July 2020
int intersectPoint(Node* head1, Node* head2) {
int c1=0;
int c2=0;
Node *temp1= head1;
Node *temp2= head2;
while (temp1) {
c1++;
temp1=temp1->next;
}
while (temp2){
c2++;
temp2=temp2->next;
}
int c = (c1-c2);
int i;
// cout <<c<< ": count\n" ;
if (c>=0) {
for (i=0;i<c;i++){
head1=head1->next;
}
} else {
c=c*-1;
for (i=0;i<c;i++){
head2=head2->next;
}
}
while (head1 != NULL && head2 != NULL) {
if (head1 == head2) {
return head1->data;
}
head1=head1->next;
head2=head2->next;
}
return -1;
}Pairwise swap elements of a linked list Solved on: Jul 22nd 2020
Node* pairWiseSwap(struct Node* head) {
Node *temp = head;
while (temp != NULL && temp->next != NULL) {
swap (temp->data, temp->next->data);
temp = temp->next->next;
}
return head;
}Last updated