Problem
The last node of a singly linklist points to the middle node of the linklist.If there are even number of nodes the first middle node is considered as the middle element.If there is only one node,it is considered as start/middle/end node.How will you delete the given data in the linklist ?
After deleting, the last node should still point to the middle node of the updated linklist.
Example:
1,2,3,4,5
Here 5 points to 3
If 4 is deleted
1,2,3,5
Now 5 points to 2
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Last node should still point to the middle node of the updated linklist
Created Date : 17-August-2013
Last Modified :
===========================================================================
*/
#include <iostream>
#include <iomanip>
#include <cassert>
using namespace std;
typedef struct linkedNode{
int data;
int len;
struct linkedNode *next;
} LINKEDNODE;
void AddNode(LINKEDNODE** head, int data)
{
LINKEDNODE* node = new LINKEDNODE;
node->data = data;
if(*head == NULL){
*head = node;
(*head)->len = 1;
(*head)->next = node;
return;
}
int index(0);
int len = (*head)->len;
LINKEDNODE* n = *head;
while(true){
index ++;
if(index == len) break;
n = n->next;
}
// update middle node and len
LINKEDNODE* prev_mid = n->next;
n->next = node;
(*head)->len ++;
node->next = ((*head)->len % 2 == 0) ? prev_mid : prev_mid->next;
}
bool DeleteNode(LINKEDNODE** head, int data)
{
if(*head == NULL) return false;
LINKEDNODE *node = *head;
int len = (*head)->len;
if(node->data == data && node->len == 1){ // Delete last node in the list
delete node;
*head = NULL;
return true;
}
bool found(false);
if(node->data == data && *head == node ){ // Delete head node
*head = node->next;
delete node;
found = true;
}
else{
int index(0);
while(index < len){
if(node->next->data == data){
LINKEDNODE *n = node->next;
node->next = n->next;
delete n;
found = true;
break;
}
node = node->next;
index ++;
}
}
if(!found) return false;
// update len and last node
len --;
(*head)->len = len;
int mid = (len - 1) / 2;
int index(0);
LINKEDNODE* midNode;
node = *head;
while(index < len){
if(index == mid) midNode = node;
if(index == len - 1) break;
index ++;
node = node->next;
}
node->next = midNode;
return true;
}
void CreatLinkedList(LINKEDNODE** head, int* arr, int len)
{
assert(arr != NULL && len > 0);
for(int i = 0; i < len; ++i){
AddNode(head, arr[i]);
}
}
void DeleteLinkedList(LINKEDNODE *head)
{
if(head == NULL) return;
int len = head->len;
LINKEDNODE *n = head;
LINKEDNODE *h = head;
while(1){
n = h->next;
delete h;
len --;
if(len == 0) break;
h = n;
}
}
void DisplayList(LINKEDNODE* head)
{
if(head != NULL){
int len = head->len;
int index(0);
while(index < len){
cout << setw(4) << head->data << " ";
head = head->next;
index ++;
}
}
cout << endl;
}
bool MidNodeValue(LINKEDNODE* head, int& midValue)
{
if(head != NULL){
int len = head->len;
int index(0);
while(index < len){
index ++;
head = head->next;
}
midValue = head->data;
return true;
}
return false;
}
void DoTest(LINKEDNODE** head, int data)
{
cout << "The list before deleting is ";
DisplayList(*head);
cout << "The node to delete is " << data << endl;
int midValue;
if(MidNodeValue(*head, midValue)){
cout << "\nMid value is " << midValue << endl;
}
else{
cout << "The linked list is empty" << endl;
}
if(DeleteNode(head, data)){
cout << "The list after deleting is ";
DisplayList(*head);
if(MidNodeValue(*head, midValue)){
cout << "\nMid value is " << midValue << endl;
}
else{
cout << "The linked list is empty" << endl;
}
}
else{
cout << "Could not find the node with data: " << data << endl;
}
cout << "--------------------------" << endl;
}
int main(int argc, char* argv[])
{
LINKEDNODE *head = NULL;
int arr[] = {1, 2, 3, 4, 5};
CreatLinkedList(&head, arr, sizeof(arr)/sizeof(int));
DoTest(&head, 1);
AddNode(&head, 6);
DoTest(&head, 4);
DoTest(&head, 6);
DoTest(&head, 6);
DoTest(&head, 5);
DoTest(&head, 3);
DoTest(&head, 2);
DoTest(&head, 2);
return 0;
}
Output
The list before deleting is 1 2 3 4 5
The node to delete is 1
Mid value is 3
The list after deleting is 2 3 4 5
Mid value is 3
--------------------------
The list before deleting is 2 3 4 5 6
The node to delete is 4
Mid value is 4
The list after deleting is 2 3 5 6
Mid value is 3
--------------------------
The list before deleting is 2 3 5 6
The node to delete is 6
Mid value is 3
The list after deleting is 2 3 5
Mid value is 3
--------------------------
The list before deleting is 2 3 5
The node to delete is 6
Mid value is 3
Could not find the node with data: 6
--------------------------
The list before deleting is 2 3 5
The node to delete is 5
Mid value is 3
The list after deleting is 2 3
Mid value is 2
--------------------------
The list before deleting is 2 3
The node to delete is 3
Mid value is 2
The list after deleting is 2
Mid value is 2
--------------------------
The list before deleting is 2
The node to delete is 2
Mid value is 2
The list after deleting is
The linked list is empty
--------------------------
The list before deleting is
The node to delete is 2
The linked list is empty
Could not find the node with data: 2
--------------------------
Press any key to continue . . .