Write a c# program to find the sum of the series 1 +11 + 111 + 1111 + .. n terms.

Author Bio

Inhaltsverzeichnis Show

Nora Sandler is a software engineer. After graduating from the University of Chicago, she worked as a penetration tester at Security Innovation, and then as a compiler developer at CrowdStrike, fuelling her interest and research into how computers work under the hood. Sandler writes C Compiler tutorials and has created test programs on her popular blog to make writing a C compiler more accessible.

Table of contents

Introduction
Part I: The Basics
1. Introduction to Compilers
2. Returning an Integer
3. Unary Operators
4. Binary Operators
5. Logical and Relational Operators
6. Local Variables
7. If Statements and Conditional Expressions
8. Compound Statements
9. Loops
10. Functions
11. Static Variables
Part II: Implementing Types
12. Long Integers
13. Unsigned Integers
14. Floating-point numbers
15. Pointers
16. Arrays and Pointer Arithmetic
17. Characters and Strings
18. Supporting Dynamic Memory Allocation
19. Structures
Part III: Optimizations
20. Optimizing TACKY Programs
21. Register Allocation
Conclusion: Next Steps

The chapters in red are included in this Early Access PDF.

Reviews

"It is refreshing to read a book on compiler design with a focus on implementing a practical real-world language, rather than working through dry academic exercises . . . practical, fun, and exciting to read if you are sick of reading textbooks on the subject."
—Rick Battagline, author of The Art of WebAssembly

Given a singly linked list, find the middle of the linked list. For example, if the given linked list is 1->2->3->4->5 then the output should be 3.
If there are even nodes, then there would be two middle nodes, we need to print the second middle element. For example, if the given linked list is 1->2->3->4->5->6 then the output should be 4.

Method 1: Traverse the whole linked list and count the no. of nodes. Now traverse the list again till count/2 and return the node at count/2.
Below is the implementation of the above approach:

C++

#include <iostream>

using namespace std;

class Node {

public:

int data;

Node* next;

};

class NodeOperation {

public:

void pushNode(class Node** head_ref, int data_val)

{

class Node* new_node = new Node();

new_node->data = data_val;

new_node->next = *head_ref;

*head_ref = new_node;

}

void printNode(class Node* head)

{

while (head != NULL) {

cout << head->data << "->";

head = head->next;

}

cout << "NULL" << endl;

}

int getLen(class Node* head)

{

int len = 0;

class Node* temp = head;

while (temp) {

len++;

temp = temp->next;

}

return len;

}

void printMiddle(class Node* head)

{

if (head) {

int len = getLen(head);

class Node* temp = head;

int midIdx = len / 2;

while (midIdx--) {

temp = temp->next;

}

cout << "The middle element is [" << temp->data

<< "]" << endl;

}

};

int main()

{

class Node* head = NULL;

class NodeOperation* temp = new NodeOperation();

for (int i = 5; i > 0; i--) {

temp->pushNode(&head, i);

temp->printNode(head);

temp->printMiddle(head);

}

return 0;

}

Java

class GFG {

Node head;

class Node {

int data;

Node next;

public Node(int data)

{

this.data = data;

this.next = null;

}

public void pushNode(int data)

{

Node new_node = new Node(data);

new_node.next = head;

head = new_node;

}

public void printNode()

{

Node temp = head;

while (temp != null) {

System.out.print(temp.data + "->");

temp = temp.next;

}

System.out.print("Null"+"\n");

}

public int getLen()

{

int length = 0;

Node temp = head;

while (temp != null) {

length++;

temp = temp.next;

}

return length;

}

public void printMiddle()

{

if (head != null) {

int length = getLen();

Node temp = head;

int middleLength = length / 2;

while (middleLength != 0) {

temp = temp.next;

middleLength--;

}

System.out.print("The middle element is ["

+ temp.data + "]");

System.out.println();

}

public static void main(String[] args)

{

GFG list = new GFG();

for (int i = 5; i >= 1; i--) {

list.pushNode(i);

list.printNode();

list.printMiddle();

}

Python3

class Node:

def __init__(self, data):

self.data = data

self.next = None

class NodeOperation:

def pushNode(self, head_ref, data_val):

new_node = Node(data_val)

new_node.next = head_ref

head_ref = new_node

return head_ref

def printNode(self, head):

while (head != None):

print('%d->' % head.data, end="")

head = head.next

print("NULL")

def getLen(self, head):

temp = head

len = 0

while (temp != None):

len += 1

temp = temp.next

return len

def printMiddle(self, head):

if head != None:

len = self.getLen(head)

temp = head

midIdx = len // 2

while midIdx != 0:

temp = temp.next

midIdx -= 1

print('The middle element is [%d]' % temp.data)

head = None

temp = NodeOperation()

for i in range(5, 0, -1):

head = temp.pushNode(head, i)

temp.printNode(head)

temp.printMiddle(head)

C#

using System;

public class GFG {

class Node {

public int data;

public Node next;

public Node(int data)

{

this.data = data;

this.next = null;

}

Node head;

public void pushNode(int data)

{

Node new_node = new Node(data);

new_node.next = head;

head = new_node;

}

public void printNode()

{

Node temp = head;

while (temp != null) {

Console.Write(temp.data + "->");

temp = temp.next;

}

Console.Write("Null"

+ "\n");

}

public int getLen()

{

int length = 0;

Node temp = head;

while (temp != null) {

length++;

temp = temp.next;

}

return length;

}

public void printMiddle()

{

if (head != null) {

int length = getLen();

Node temp = head;

int middleLength = length / 2;

while (middleLength != 0) {

temp = temp.next;

middleLength--;

}

Console.Write("The middle element is ["

+ temp.data + "]");

Console.WriteLine();

}

static public void Main()

{

GFG list = new GFG();

for (int i = 5; i >= 1; i--) {

list.pushNode(i);

list.printNode();

list.printMiddle();

}

Javascript

<script>

var head;

class Node {

constructor(val) {

this.data = val;

this.next = null;

}

function pushNode(new_data) {

var new_node = new Node(new_data);

new_node.next = head;

head = new_node;

}

function printNode() {

var tnode = head;

while (tnode != null) {

document.write(tnode.data + "->");

tnode = tnode.next;

}

document.write("NULL<br/>");

}

function getLen(){

let length = 0;

var temp = head;

while(temp!=null){

length+=1;

temp = temp.next;

}

return length;

}

function printMiddle(){

if(head!=null){

let length = getLen();

var temp = head;

let middleLength = length/2;

while(parseInt(middleLength)!=0){

temp = temp.next;

middleLength--;

}

document.write("The middle element is [" + temp.data + "]<br/><br/>");

}

for (let i = 5; i >= 1; --i) {

pushNode(i);

printNode();

printMiddle();

}

</script>

Output

5->NULL
The middle element is [5]
4->5->NULL
The middle element is [5]
3->4->5->NULL
The middle element is [4]
2->3->4->5->NULL
The middle element is [4]
1->2->3->4->5->NULL
The middle element is [3]

Time Complexity: O(n) where n is no of nodes in linked list

Auxiliary Space: O(1)

Method 2: Traverse linked list using two-pointers. Move one pointer by one and the other pointers by two. When the fast pointer reaches the end, the slow pointer will reach the middle of the linked list.

Below image shows how printMiddle function works in the code :

C++

#include <iostream>

using namespace std;

class Node{

public:

int data;

Node *next;

};

class NodeOperation{

public:

void pushNode(class Node** head_ref,int data_val){

class Node *new_node = new Node();

new_node->data = data_val;

new_node->next = *head_ref;

*head_ref = new_node;

}

void printNode(class Node *head){

while(head != NULL){

cout <<head->data << "->";

head = head->next;

}

cout << "NULL" << endl;

}

void printMiddle(class Node *head){

struct Node *slow_ptr = head;

struct Node *fast_ptr = head;

if (head!=NULL)

{

while (fast_ptr != NULL && fast_ptr->next != NULL)

{

fast_ptr = fast_ptr->next->next;

slow_ptr = slow_ptr->next;

}

cout << "The middle element is [" << slow_ptr->data << "]" << endl;

}

};

int main(){

class Node *head = NULL;

class NodeOperation *temp = new NodeOperation();

for(int i=5; i>0; i--){

temp->pushNode(&head, i);

temp->printNode(head);

temp->printMiddle(head);

}

return 0;

}

C

#include<stdio.h>

#include<stdlib.h>

struct Node

{

int data;

struct Node* next;

};

void printMiddle(struct Node *head)

{

struct Node *slow_ptr = head;

struct Node *fast_ptr = head;

if (head!=NULL)

{

while (fast_ptr != NULL && fast_ptr->next != NULL)

{

fast_ptr = fast_ptr->next->next;

slow_ptr = slow_ptr->next;

}

printf("The middle element is [%d]\n\n", slow_ptr->data);

}

void push(struct Node** head_ref, int new_data)

{

struct Node* new_node =

(struct Node*) malloc(sizeof(struct Node));

new_node->data = new_data;

new_node->next = (*head_ref);

(*head_ref) = new_node;

}

void printList(struct Node *ptr)

{

while (ptr != NULL)

{

printf("%d->", ptr->data);

ptr = ptr->next;

}

printf("NULL\n");

}

int main()

{

struct Node* head = NULL;

int i;

for (i=5; i>0; i--)

{

push(&head, i);

printList(head);

printMiddle(head);

}

return 0;

}

Java

class LinkedList

{

Node head;

class Node

{

int data;

Node next;

Node(int d)

{

data = d;

next = null;

}

void printMiddle()

{

Node slow_ptr = head;

Node fast_ptr = head;

while (fast_ptr != null && fast_ptr.next != null)

{

fast_ptr = fast_ptr.next.next;

slow_ptr = slow_ptr.next;

}

System.out.println("The middle element is [" +

slow_ptr.data + "] \n");

}

public void push(int new_data)

{

Node new_node = new Node(new_data);

new_node.next = head;

head = new_node;

}

public void printList()

{

Node tnode = head;

while (tnode != null)

{

System.out.print(tnode.data+"->");

tnode = tnode.next;

}

System.out.println("NULL");

}

public static void main(String [] args)

{

LinkedList llist = new LinkedList();

for (int i=5; i>0; --i)

{

llist.push(i);

llist.printList();

llist.printMiddle();

}

C#

using System;

class LinkedList{

Node head;

class Node

{

public int data;

public Node next;

public Node(int d)

{

data = d;

next = null;

}

void printMiddle()

{

Node slow_ptr = head;

Node fast_ptr = head;

if (head != null)

{

while (fast_ptr != null &&

fast_ptr.next != null)

{

fast_ptr = fast_ptr.next.next;

slow_ptr = slow_ptr.next;

}

Console.WriteLine("The middle element is [" +

slow_ptr.data + "] \n");

}

public void push(int new_data)

{

Node new_node = new Node(new_data);

new_node.next = head;

head = new_node;

}

public void printList()

{

Node tnode = head;

while (tnode != null)

{

Console.Write(tnode.data + "->");

tnode = tnode.next;

}

Console.WriteLine("NULL");

}

static public void Main()

{

LinkedList llist = new LinkedList();

for(int i = 5; i > 0; --i)

{

llist.push(i);

llist.printList();

llist.printMiddle();

}

Python3

class Node:

def __init__(self, data):

self.data = data

self.next = None

class LinkedList:

def __init__(self):

self.head = None

def push(self, new_data):

new_node = Node(new_data)

new_node.next = self.head

self.head = new_node

def printList(self):

node = self.head

while node:

print(str(node.data) + "->", end="")

node = node.next

print("NULL")

def printMiddle(self):

slow = self.head

fast = self.head

while fast and fast.next:

slow = slow.next

fast = fast.next.next

print("The middle element is ", slow.data)

if __name__=='__main__':

llist = LinkedList()

for i in range(5, 0, -1):

llist.push(i)

llist.printList()

llist.printMiddle()

Javascript

<script>

var head;

class Node {

constructor(val) {

this.data = val;

this.next = null;

}

function printMiddle()

{

var slow_ptr = head;

var fast_ptr = head;

if (head != null)

{

while (fast_ptr != null &&

fast_ptr.next != null)

{

fast_ptr = fast_ptr.next.next;

slow_ptr = slow_ptr.next;

}

document.write(

"The middle element is [" + slow_ptr.data + "] <br/><br/>"

);

}

function push(new_data) {

var new_node = new Node(new_data);

new_node.next = head;

head = new_node;

}

function printList() {

var tnode = head;

while (tnode != null) {

document.write(tnode.data + "->");

tnode = tnode.next;

}

document.write("NULL<br/>");

}

for (i = 5; i > 0; --i) {

push(i);

printList();

printMiddle();

}

</script>

Output

5->NULL
The middle element is [5]
4->5->NULL
The middle element is [5]
3->4->5->NULL
The middle element is [4]
2->3->4->5->NULL
The middle element is [4]
1->2->3->4->5->NULL
The middle element is [3]

Time Complexity: O(N), As we are traversing the list only once.
Auxiliary Space: O(1), As constant extra space is used.

Method 3: Initialize the mid element as head and initialize a counter as 0. Traverse the list from the head, while traversing increment the counter and change mid to mid->next whenever the counter is odd. So the mid will move only half of the total length of the list.
Thanks to Narendra Kangralkar for suggesting this method.

C++

#include <bits/stdc++.h>

using namespace std;

struct node

{

int data;

struct node* next;

};

void printMiddle(struct node* head)

{

int count = 0;

struct node* mid = head;

while (head != NULL)

{

if (count & 1)

mid = mid->next;

++count;

head = head->next;

}

if (mid != NULL)

printf("The middle element is [%d]\n\n",

mid->data);

}

void push(struct node** head_ref, int new_data)

{

struct node* new_node = (struct node*)malloc(

sizeof(struct node));

new_node->data = new_data;

new_node->next = (*head_ref);

(*head_ref) = new_node;

}

void printList(struct node* ptr)

{

while (ptr != NULL)

{

printf("%d->", ptr->data);

ptr = ptr->next;

}

printf("NULL\n");

}

int main()

{

struct node* head = NULL;

int i;

for(i = 5; i > 0; i--)

{

push(&head, i);

printList(head);

printMiddle(head);

}

return 0;

}

C

#include <stdio.h>

#include <stdlib.h>

struct node {

int data;

struct node* next;

};

void printMiddle(struct node* head)

{

int count = 0;

struct node* mid = head;

while (head != NULL) {

if (count & 1)

mid = mid->next;

++count;

head = head->next;

}

if (mid != NULL)

printf("The middle element is [%d]\n\n", mid->data);

}

void push(struct node** head_ref, int new_data)

{

struct node* new_node

= (struct node*)malloc(sizeof(struct node));

new_node->data = new_data;

new_node->next = (*head_ref);

(*head_ref) = new_node;

}

void printList(struct node* ptr)

{

while (ptr != NULL) {

printf("%d->", ptr->data);

ptr = ptr->next;

}

printf("NULL\n");

}

int main()

{

struct node* head = NULL;

int i;

for (i = 5; i > 0; i--) {

push(&head, i);

printList(head);

printMiddle(head);

}

return 0;

}

Java

class GFG{

static Node head;

class Node

{

int data;

Node next;

public Node(Node next, int data)

{

this.data = data;

this.next = next;

}

void printMiddle(Node head)

{

int count = 0;

Node mid = head;

while (head != null)

{

if ((count % 2) == 1)

mid = mid.next;

++count;

head = head.next;

}

if (mid != null)

System.out.println("The middle element is [" +

mid.data + "]\n");

}

void push(Node head_ref, int new_data)

{

Node new_node = new Node(head_ref, new_data);

head = new_node;

}

void printList(Node head)

{

while (head != null)

{

System.out.print(head.data + "-> ");

head = head.next;

}

System.out.println("null");

}

public static void main(String[] args)

{

GFG ll = new GFG();

for(int i = 5; i > 0; i--)

{

ll.push(head, i);

ll.printList(head);

ll.printMiddle(head);

}

Python3

class Node:

def __init__(self, data):

self.data = data

self.next = None

class LinkedList:

def __init__(self):

self.head = None

def push(self, new_data):

new_node = Node(new_data)

new_node.next = self.head

self.head = new_node

def printList(self):

node = self.head

while node:

print(str(node.data) + "->", end = "")

node = node.next

print("NULL")

def printMiddle(self):

count = 0

mid = self.head

heads = self.head

while(heads != None):

if count&1:

mid = mid.next

count += 1

heads = heads.next

if mid!=None:

print("The middle element is ", mid.data)

if __name__=='__main__':

llist = LinkedList()

for i in range(5, 0, -1):

llist.push(i)

llist.printList()

llist.printMiddle()

C#

using System;

public class GFG

{

static Node head;

public

class Node {

public

int data;

public

Node next;

public Node(Node next, int data) {

this.data = data;

this.next = next;

}

void printMiddle(Node head) {

int count = 0;

Node mid = head;

while (head != null) {

if ((count % 2) == 1)

mid = mid.next;

++count;

head = head.next;

}

if (mid != null)

Console.WriteLine("The middle element is [" + mid.data + "]\n");

}

public void Push(Node head_ref, int new_data) {

Node new_node = new Node(head_ref, new_data);

head = new_node;

}

void printList(Node head) {

while (head != null) {

Console.Write(head.data + "-> ");

head = head.next;

}

Console.WriteLine("null");

}

public static void Main(String[] args) {

GFG ll = new GFG();

for (int i = 5; i > 0; i--) {

ll.Push(head, i);

ll.printList(head);

ll.printMiddle(head);

}

Javascript

<script>

var head=null;

class Node {

constructor(next,val) {

this.data = val;

this.next = next;

}

function printMiddle(head) {

var count = 0;

var mid = head;

while (head != null) {

if ((count % 2) == 1)

mid = mid.next;

++count;

head = head.next;

}

if (mid != null)

document.write("The middle element is [" + mid.data + "]<br/><br/>");

}

function push(head_ref , new_data) {

var new_node = new Node(head_ref, new_data);

head = new_node;

return head;

}

function printList(head) {

while (head != null) {

document.write(head.data + "-> ");

head = head.next;

}

document.write("null<br/>");

}

for (i = 5; i > 0; i--) {

head= push(head, i);

printList(head);

printMiddle(head);

}

</script>

Output

5->NULL
The middle element is [5]

4->5->NULL
The middle element is [5]

3->4->5->NULL
The middle element is [4]

2->3->4->5->NULL
The middle element is [4]

1->2->3->4->5->NULL
The middle element is [3]

Time Complexity: O(N), As we are traversing the list once.
Auxiliary Space: O(1), As constant extra space is used.