Modify contents of Linked List

Problem Statement

In this problem, we would be given a linked list, and we need to modify the values of the first half nodes such that the value of the ith node will be equal to the value of (N-i-1)th node minus the value of the ith node.

Note: If the number of nodes is odd, then the value of the middle node will remain unchanged.

Problem Statement Understanding

To understand this problem statement, let us take examples by referring the best online programming courses.

If the given linked list is :

then according to the problem statement:

  • At first, focus on the first and last node and change the value of the first node to (22 - 3) = 19.
  • Then for the second node, its value will be updated to the value equal to the last-second node value minus the value of the second node, i.e., (18-12) = 6.
  • Similarly, the value of the third node will be (5-1) = 4.
  • So, the final linked list after modification will be:

Let us take another example:
If the linked list is 4→1→10→42→5→NULL.

  • After changing the values of the first half of nodes in the fashion mentioned above, our output linked list will be 1→41→10→42→5→NULL
  • Note that the number of nodes in the linked list is odd, so we will not change the middle node, i.e., node 10.

Now, I think the problem statement is clear, so let's see how we can approach it. Any ideas? If not, it's okay, and we will see how we can approach it in the next section.

Approach 1

  • Find the first element of the second half of the linked list, i.e., find the middle node of the linked list.
  • Push all elements starting from the node found above till the last of the linked list into a stack.
  • Now using a temporary pointer, temp iterate the linked list starting from the head until the stack is not empty and modify temp→data by doing temp→data = (s.top() - temp→data) and then pop the element from the stack.
  • Finally, when the traversal is over, we will have our final modified list as per the problem statement.

Algorithm 1

  • Initialize two pointers with the head of the list and name them slow and fast.
  • Find the mid-node of the list by moving the slow pointer one node at a time and the fast pointer two nodes at a time, till fast or fast →next are not NULL.
  • Now once you reach the end, check whether the fast pointer is NULL or not
    • If it is NULL then the number of nodes in the list is even, then no need to update the slow pointer as it will point to the first element of the second half of the list.
    • If it is not NULL that means the number of nodes in the list is odd so, to point to the first element of the second half of the list, we need to move the slow pointer by one node.
  • Now, we have the starting point of the second half of the list so, we will start iterating the list from here and push all data of nodes in the stack till the end of the list.
  • Now, we will begin an iteration from the starting of the list and change the value of each node to the difference of the stack’s top element and the current node at which we are in the iteration, and then we will pop the element from the stack.
  • We will repeat the above step till the stack is not empty.

We will get our desired list by following the above steps.

Time complexity: O(n), Where n is the number of nodes in the list.
Space Complexity: O(n), Where n is the number of nodes in the list

As you can see that in the above approach, we used an extra space of O(n) because we were pushing the elements of the second half of the list in the stack.

Can we improve this to constant extra space?

  • The answer is yes, we can improve our algorithm, refer below to get an idea of the constant extra space approach.

Helpful Observations

  • Notice that we cannot move backward in a linked list, so we need to devise a way by which we can traverse the list in forward and backward directions.
  • This can be only done if we first break the list from the middle into two parts and then reverse the second half.
  • After doing this, we can treat each half as two different lists, and moving forward in the second half of the list would eventually mean to iterate in the list in the backward direction as it is reversed.
  • Then, we can keep one pointer at the starting of each half, modify the nodes’ values that belong to the first half, and advance each pointer to the next node.

Approach 2

Our approach will be simple:

  • Find the middle node of the linked list and then split the linked list from the middle with the help of a fast and a slow pointer, where the slow will move one node at a time and the fast one will move 2 nodes at a time, so that when fast will be at the end of the list slow will be at the middle.
  • Now, reverse the second half of the list obtained in the above step.
  • Initialize two pointers named front and back with the starting of each list, respectively.
  • Iterate over both the lists simultaneously and update the values of the first half nodes as directed in the problem statement.
  • Then again, reverse the second half of the list.
  • Then join the two parts (first half and second half) of the list as they were originally given to us.

Algorithm 2

  • At first, we will find the middle node of our linked list and then break the list from there.
  • Then, we will have two different linked lists.
  • Then, we will reverse the second linked list.
  • Initialize two pointers, front and back, where the front will point to the first node of the first list and the back will point to the first node of the second list.
  • While the end of the second list is not reached i.e., back is not equal to NULL pointer, we need to iterate the list and do the following:
    a) Change front’s data to the difference of back’s and front’s data (front->data = back->data - front->data).
    b) Advance front pointer by one node (front = front->next).
    c) Advance back pointer by one node (front = front->next).
  • After the while loop ends, reverse the second list again.
  • Now, attach the second list to the end of the first list.
  • Return the head of the newly created list.
  • The first half nodes of the returned list will be modified according to the problem statement.

Dry Run

Code Implementation

#include
using namespace std;
class Node
{
    public:
    int data;
    Node* next;
    Node(int x){
        data = x;
   next = NULL;
    }
};
 
 
void midPartition(Node *head,
               Node **front_ref, Node **back_ref)
{
    Node *slow, *fast;
     
    slow = head;
    fast = head->next;
     
    /* Advance 'fast' pointer two nodes at a time and
       advance 'slow' pointer one node at a time */
    while (fast != NULL)
    {
        fast = fast->next;
        if (fast != NULL)
        {
            slow = slow->next;
            fast = fast->next;
        }
    }
     
     /* 'slow' is before the midpoint in the list,
        so split it in two at that point. */
    *front_ref = head;
    *back_ref = slow->next;
    slow->next = NULL;
}

void reverseList(Node **head_ref)
{
    Node *current, *prev, *next;
    current = *head_ref;
    prev = NULL;
    while (current != NULL)
    {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }   
    *head_ref = prev;
}
void modifyContent(Node *head1,Node *head2)
{
    Node *front = head1, *back = head2;
    // traverse both the lists simultaneously
    while (back != NULL)
    {
        front->data = back->data - front->data;
         
        front = front->next;
        back = back->next;
    }
}

void printList(Node *head)
{
    if (!head)
        return;
     
    while (head->next != NULL)
    {
        cout << head->data << " ";
        head = head->next;
    }
    cout << head->data << endl;
}
 
Node* concatFrontAndBackList(Node *front,
                                    Node *back)
{
    Node *head = front;
 
    while (front->next != NULL)
        front = front->next;   
         
    front->next = back;
     
    return head;
}

Node* solve(Node *head)
{
 // if list is empty or contains only single node then return it
    if (!head || head->next == NULL)
        return head;
     
    Node *front, *back;
     
    // split the list into two parts
    midPartition(head, &front, &back);   
         
    // reverse the 2nd half of the list
    reverseList(&back);
     
    // modify the contents of 1st half of the list  
    modifyContent(front, back);
         
    // again reverse the 2nd half of list
    reverseList(&back);
     
    // concatenate both the halves to get the original list
    // that was provided initially
    head = concatFrontAndBackList(front, back);
     
    // pointer to the modified list
    return head;
}
int main(void)
{
    Node* head = NULL;
    head = new Node(3);
    head->next = new Node(12);
    head->next->next = new Node(1);
    head->next->next->next = new Node(5);
    head->next->next->next->next = new Node(18);
    head->next->next->next->next->next = new Node(22);
    
    Node *tmp = solve(head);
    printList(tmp);
    return 0;
}
#include 
#include
#include
 
struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
};

void push(struct Node** head_ref, int new_c)
{
    struct Node* new_node =
            (struct Node*) malloc(sizeof(struct Node));
    new_node->data = new_c;
    new_node->prev = NULL;
    new_node->next = (*head_ref);
    if ((*head_ref) != NULL)
        (*head_ref)->prev = new_node;
     *head_ref = new_node;
}

bool isCircular(struct Node *head){
 struct Node *temp=head;
 while(temp!=NULL)
 { //if temp points to head then it has completed a circle,thus a circular linked list.
    if(temp->next==head)
        return true;
    temp=temp->next;
}

return false;

}
int main(void)
{
    struct Node* head = NULL;
    push(&head, 5);
    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);
    
    if(isCircular(head))
		printf("Yes\n");
	else
		printf("No\n");
 
}


class Modify
{
    static class Node
    {
	    int data;
	    Node next;
    };
    static Node push(Node head_ref, int new_data)
    {
	    Node new_node =new Node();
        new_node.data = new_data;
	    new_node.next = head_ref;
	    head_ref = new_node;
	
	    return head_ref;
    }
    static Node front,back;
    /* Split the nodes of the given list into front and back halves,
    and return the two lists using the reference parameters.
    Uses the fast/slow pointer strategy. */
    static void frontAndBackSplit( Node head)
    {
	    Node slow, fast;
	
	    slow = head;
	    fast = head.next;
	
	    /* Advance 'fast' two nodes, and
	    advance 'slow' one node */
	    while (fast != null)
	    {
		    fast = fast.next;
		    if (fast != null)
		    {
			    slow = slow.next;
			    fast = fast.next;
		    }
        }
	    /* 'slow' is before the midpoint in the list,
		so split it in two at that point. */
	    front = head;
	    back = slow.next;
	    slow.next = null;
    }
    /* Function to reverse the linked list */
    static Node reverseList( Node head_ref)
    {
	    Node current, prev, next;
	    current = head_ref;
	    prev = null;
	    while (current != null)
	    {
		    next = current.next;
		    current.next = prev;
		    prev = current;
		    current = next;
	    }
	    head_ref = prev;
	    return head_ref;
    }   
    // perform the required subtraction operation on the 1st half of the linked list
    static void modifyTheContentsOf1stHalf()
    {
	    Node front1 = front, back1 = back;
	    // traversing both the lists simultaneously
	    while (back1 != null)
	    {
		    // subtraction operation and node data modification
		    front1.data = front1.data - back1.data;
		    front1 = front1.next;
		    back1 = back1.next;
	    }
    }
    // function to concatenate the 2nd(back) list
    // at the end of the 1st(front) list and
    // returns the head of the new list
    static Node concatFrontAndBackList(Node front,Node back)
    {
	    Node head = front;
	
	    if(front == null)return back;
	
	    while (front.next != null)
		    front = front.next;
		
	    front.next = back;
	
	    return head;
    }
    // function to modify the contents of the linked list
    static Node modifyTheList( Node head)
    {
	    // if list is empty or contains only single node
	    if (head == null || head.next == null)
		    return head;
	    front = null; back = null;
	
	    // split the list into two halves front and back lists
	    frontAndBackSplit(head);
		
	    back = reverseList(back);
	    // modify the contents of 1st half
	    modifyTheContentsOf1stHalf();
	
	    // agains reverse the 2nd(back) list
	    back = reverseList(back);

	    head = concatFrontAndBackList(front, back);

	    return head;
    }
    static void printList( Node head)
    {
	    if (head == null)
	        return;
	
	    while (head.next != null)
	    {
		    System.out.print(head.data + " -> ");
		    head = head.next;
	    }
	    System.out.println(head.data );
    }
    // Driver Code
    public static void main(String args[])
    {
	    Node head = null;
	
	    // creating the linked list
	    head = push(head, 10);
	    head = push(head, 7);
	    head = push(head, 12);
	    head = push(head, 8);
	    head = push(head, 9);
	    head = push(head, 2);
	
	    // modify the linked list
	    head = modifyTheList(head);
	
	    // print the modified linked list
	    System.out.println( "Modified List:" );
	    printList(head);
    }
}

// This code is contributed by Arnab Kundu



class Node:
	
	def __init__(self, data):
		self.data = data
		self.next = None

def push(head_ref, new_data):

	new_node =Node(0)
	new_node.data = new_data
	new_node.next = head_ref
	head_ref = new_node
	return head_ref

front = None
back = None

def frontAndBackSplit( head):

	global front
	global back
	slow = None
	fast = None
	
	slow = head
	fast = head.next
	
	while (fast != None):
	
		fast = fast.next
		if (fast != None):
			slow = slow.next
			fast = fast.next

	front = head
	back = slow.next
	slow.next = None
	return head

def reverseList( head_ref):

	current = None
	prev = None
	next = None
	current = head_ref
	prev = None
	while (current != None):
	
		next = current.next
		current.next = prev
		prev = current
		current = next
	
	head_ref = prev
	return head_ref

def modifyTheContentsOf1stHalf():

	global front
	global back
	front1 = front
	back1 = back
	
	while (back1 != None):
	
		front1.data = (back1.data - front1.data)
		front1 = front1.next
		back1 = back1.next
	
def concatFrontAndBackList( front, back):
	
	head = front
	
	if(front == None):
		return back
	
	while (front.next != None):
		front = front.next
		
	front.next = back
	return head

def modifyTheList( head):

	global front
	global back

	if (head == None or head.next == None):
		return head
	front = None
	back = None
	
	frontAndBackSplit(head)
	back = reverseList(back)
	modifyTheContentsOf1stHalf()
	back = reverseList(back)
	head = concatFrontAndBackList(front, back)
	return head

def printList( head):

	if (head == None):
		return
	
	while (head.next != None):
	
		print(head.data ,end=" ")
		head = head.next
	
	print(head.data )

head = None
	
head = push(head, 22)
head = push(head, 18)
head = push(head, 5)
head = push(head, 1)
head = push(head, 12)
head = push(head, 3)
	
head = modifyTheList(head)
	
printList(head)

Output

19 6 4 5 18 22

Time complexity: O(n), Where n is the number of nodes in the list.
[forminator_quiz id="4649"]

So, in this blog, we have tried to explain how you can modify the contents of a linked list in the most optimal way. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Leave a Reply

Your email address will not be published. Required fields are marked *