Monday, February 7, 2022

K Reverse In Linked List

I/O:

11

1 2 3 4 5 6 7 8 9 10 11

3

100

200


O/P:

1 2 3 4 5 6 7 8 9 10 11 3 2 1 6 5 4 9 8 7 10 11 100 3 2 1 6 5 4 9 8 7 10 11 200

img



import java.io.BufferedReader;
import java.io.InputStreamReader;

public class K_Reverse_In_LinkedList {
public static class Node {
int data;
Node next;
}

public static class LinkedList {
Node head;
Node tail;
int size;

void addLast(int val) {
Node temp = new Node();
temp.data = val;
temp.next = null;

if (size == 0) {
head = tail = temp;
} else {
tail.next = temp;
tail = temp;
}

size++;
}

public int size() {
return size;
}

public void display() {
for (Node temp = head; temp != null; temp = temp.next) {
System.out.print(temp.data + " ");
}
System.out.println();
}

public void removeFirst() {
if (size == 0) {
System.out.println("List is empty");
} else if (size == 1) {
head = tail = null;
size = 0;
} else {
head = head.next;
size--;
}
}

public void addFirst(int val) {
Node temp = new Node();
temp.data = val;
temp.next = head;
head = temp;

if (size == 0) {
tail = temp;
}

size++;
}

// write your code here
public void kReverse(int k) {
LinkedList ans = new LinkedList();

while (k < size) {
LinkedList current = new LinkedList();
for (int i = 0; i < k; i++) {
current.addFirst(head.data);
this.removeFirst();
}

if (ans.size == 0) {
ans.head = current.head;
ans.tail = current.tail;
ans.size = current.size;
} else {
ans.tail = current.head;
ans.tail = current.tail;
ans.size += current.size;
}
}

while (size > 0) {
ans.addLast(head.data);
this.removeFirst();
}
head = ans.head;
tail = ans.tail;
this.size = ans.size;
}

}

public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int n1 = Integer.parseInt(br.readLine());
LinkedList l1 = new LinkedList();
String[] values1 = br.readLine().split(" ");
for (int i = 0; i < n1; i++) {
int d = Integer.parseInt(values1[i]);
l1.addLast(d);
}

int k = Integer.parseInt(br.readLine());
int a = Integer.parseInt(br.readLine());
int b = Integer.parseInt(br.readLine());

l1.display();
l1.kReverse(k);
l1.display();
l1.addFirst(a);
l1.addLast(b);
l1.display();
}
}

No comments:

Post a Comment

Diagonal Traversal

 eg.  1       2       3       4 5      6       7       8 9    10    11     12 13  14   15    16 Output: 1 6 11 16 2 7 12 3 8 4  Approach:...