Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
/**
* Created by dheeraj on 12/12/14.
*/
public class ReverseALinkedList {
public static class Node {
int value;
Node next;
public Node(int data) {
value = data;
next = null;
}
}
public static class LinkedList {
Node root;
int length;
public LinkedList() {
root = null;
length = 0;
}
public void insert(int data) {
root = insertPrivate(root, data);
length++;
}
private Node insertPrivate(Node root, int data) {
if (root == null) {
root = new Node(data);
} else {
root.next = insertPrivate(root.next, data);
}
return root;
}
public void traverse() {
traversePrivate(root);
}
private void traversePrivate(Node root) {
if (root == null) {
return;
} else {
System.out.println(root.value);
traversePrivate(root.next);
}
}
public void reverse() {
root = reversePrivate(root);
}
private Node reversePrivate(Node root) {
Node previous = null;
Node current = root;
Node next = null;
while (current != null) {
next = current.next;
current.next = previous;
previous = current;
current = next;
}
return previous;
}
public void reverseFromNthNodeFromStart(int n) {
Node temp = root;
for (int x = 1; x <= n-1; x++) {
temp = root.next;
if (temp == null) {
return;
}
}
temp.next = reversePrivate(temp.next);
}
public void reverseFromNthNodeFromEnd(int n){
reverseFromNthNodeFromStart(length-n);
}
}
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.insert(1);
linkedList.insert(2);
linkedList.insert(3);
linkedList.insert(4);
linkedList.insert(5);
linkedList.insert(6);
//linkedList.reverseFromNthNodeFromStart(2);
linkedList.reverseFromNthNodeFromEnd(5);
linkedList.traverse();
}
}
In my solution I keep track of the last N node in a List, then I attach the last node to the N-1th node in the original list and read backwards the nodes on the List containing the last N nodes. Running time O(n) and you don't have to know the length of the list of nodes in advance.
import java.util.ArrayList;
import java.util.List;
class Lnode {
int value;
Lnode next;
public Lnode (int value) {
this.value = value;
this.next=null;
}
public Lnode(int value,Lnode next) {
this(value);
this.next = next;
}
public String toString() {
return this.value+" ";
}
}
public class ReverseNthNode {
public static void printLnode(Lnode head) {
while(head!=null) {
System.out.print(head.value);
if(head.next!=null) {
System.out.print(" -> ");
}
head=head.next;
}
System.out.println();
}
public static Lnode reverseLastN(Lnode head, int n) {
if(n<=0) return head;
List<Lnode> lasts = new ArrayList<Lnode>();
Lnode prev = null;
Lnode current = head;
while(current!=null) {
if(lasts.size()>=n) {
prev = lasts.remove(0);
}
lasts.add(current);
current=current.next;
}
for(int i=lasts.size()-1;i>0;i--) {
lasts.get(i).next = lasts.get(i-1);
}
if(prev != null) {
lasts.get(0).next=null;
prev.next=lasts.get(lasts.size()-1);
return head;
}
else {
lasts.get(0).next=null;
return lasts.get(lasts.size()-1);
}
}
public static void main(String[] args) {
Lnode l7 = new Lnode(7);
Lnode l6 = new Lnode(6,l7);
Lnode l5 = new Lnode(5,l6);
Lnode l4 = new Lnode(4,l5);
Lnode l3 = new Lnode(3,l4);
Lnode l2 = new Lnode(2,l3);
Lnode l1 = new Lnode(1,l2);
printLnode(l1);
printLnode(reverseLastN(l1,5));
}
}
private LinkedList reverseLinkListRecursive(LinkedList node){
//LinkedList header=null;
if(node.getNext()==null){
return node;
}
LinkedList head=reverseLinkListRecursive(node.getNext());
node.getNext().setNext(node);
node.setNext(null);
return head;
}
private void reverseLastFive(LinkedList header){
LinkedList fastPointer=header,slowPointer=header,data=header;
int count=1;
while(fastPointer.getNext()!=null){
fastPointer=fastPointer.getNext();
if(count>=6){
slowPointer=slowPointer.getNext();
}
count++;
}
header1=reverseLinkListRecursive(slowPointer.getNext());
slowPointer.setNext(header1);
printLinkedList(header);
}
private void printLinkedList(LinkedList header){
LinkedList current=header;
while(current.getNext()!=null){
System.out.print(current.getData()+"-->");
current=current.getNext();
}
System.out.print(current.getData()+"\n");
}
public void reverseLastNnodes(int n) throws EmptyListException, InvalidPositionException{
if(this.head == null){
throw new EmptyListException("In reverse N Node : Empty exception.");
}
if(this.size < n){
throw new InvalidPositionException("Node count exception.");
}
ListNode<T> slow = this.head, fast = this.head, tem = null;
int i = 0;
while(i < (n-1)){
fast = fast.getNext();
i++;
}
while(fast.getNext() != null){
if(tem == null && fast.getNext().getNext() == null){
tem = slow;
}
slow = slow.getNext();
fast = fast.getNext();
}
tem.setNext(reverseListNodes(slow,null));
}
/**
* Utility method to reverse last n nodes
*
* @param node
* @param temp
* @return
*/
private ListNode<T> reverseListNodes(ListNode<T> node, ListNode<T> temp){
while(node != null){
ListNode<T> nextNode = null;
nextNode = node.getNext();
node.setNext(temp);
temp = node;
node = nextNode;
}
return temp;
}
Hi,
My code is a code that use recursion. It basically runs to the end of the list, and when it gets there it is starting to reverse the order of the nodes...
the complexity stays O(n) but in my opinion the code is more clear to read (and much shorter) here..
Thanks,
package neww;
public class SinglyLinkedListReverseLast5 {
public static void main(String[] args) {
Node n7 = new Node(7, null);
Node n6 = new Node(6, n7);
Node n5 = new Node(5, n6);
Node n4 = new Node(4, n5);
Node n3 = new Node(3, n4);
Node n2 = new Node(2, n3);
Node n1 = new Node(1, n2);
int numberOfNodestoReverse = 5;
System.out.println(n1.toString());
reverse(getNthElement(n1 ,numberOfNodestoReverse+1));
System.out.println(n1.toString());
}
public static Node getNthElement(Node head, int n) {
Node f_ptr = head;
Node s_ptr = head;
for (; n > 0; n--) {
f_ptr = f_ptr.next;
}
while (f_ptr != null) {
f_ptr = f_ptr.next;
s_ptr = s_ptr.next;
}
System.out.println(s_ptr.toString());
return s_ptr;
}
public static void reverse(Node curr) {
Node oldNext=curr.next;
Node newNext=reverse(curr.next,curr.next.next);
curr.next=newNext;
oldNext.next=null;
}
private static Node reverse(Node pre, Node curr) {
if (curr == null) {
return pre;
}
Node ret=reverse(curr,curr.next);
curr.next=pre;
return ret;
}
}
class Node {
int value;
Node next;
Node(int value, Node next) {
this.value = value;
this.next = next;
}
public String toString() {
String result = value + " ";
if (next != null) {
result += next.toString();
}
return result;
}
}
public void reverseN(int n)
{
if(n>this.count())
return;
Stack<Node> s= new Stack<Node>();
Node cur=head;
//traverse n nodes to point nth node
for(int i=0;i<n-1;i++)
{
cur=cur.next;
}
Node prev=head; Node old=head; Node temp=null;
while(cur.next!=null)
{
old=prev;
prev=prev.next;
cur=cur.next;
}
while(prev!=null)
{
temp=prev.next;
prev.next=null;
s.push(prev);
prev=temp;
}
while(s.size()>0)
{
old.next=s.pop();
old=old.next;
}
}
public static void main(String[] args) {
LL l = new LL();
l.insert(1); l.insert(2);l.insert(3);
l.insert(4); l.insert(5);l.insert(6);
l.insert(7);
l.display(); System.out.println();
l.reverseN(5);
l.display();
}
public void reverseN(int n)
{
if(n>this.count())
return;
Stack<Node> s= new Stack<Node>();
Node cur=head;
//traverse n nodes to point nth node
for(int i=0;i<n-1;i++)
{
cur=cur.next;
}
Node prev=head; Node old=head; Node temp=null;
while(cur.next!=null)
{
old=prev;
prev=prev.next;
cur=cur.next;
}
while(prev!=null)
{
temp=prev.next;
prev.next=null;
s.push(prev);
prev=temp;
}
while(s.size()>0)
{
old.next=s.pop();
old=old.next;
}
}
public static void main(String[] args) {
LL l = new LL();
l.insert(1); l.insert(2);l.insert(3);
l.insert(4); l.insert(5);l.insert(6);
l.insert(7);
l.display(); System.out.println();
l.reverseN(7);
l.display();
}
}}
Rough solution, yes we can do some more optimization but I believe code readability is great
class Node
attr_accessor :value, :next_node
def initialize(value, next_node)
@value = value
@next_node = next_node
end
end
class Linkedlist
def initialize(value)
@head = Node.new(value, nil)
end
def add_node(value)
current = @head
while current.next_node != nil
current = current.next_node
end
current.next_node = Node.new(value, nil)
end
def display
current = @head
list = []
while current.next_node != nil
list += [current.value.to_s]
current = current.next_node
end
list += [current.value.to_s]
puts "LINKEDLISTS ARE #{list.join("=>")}"
end
def reverse_link_list(value_to_reverse)
current = @head
list = []
while current.next_node != nil
list += [current.value.to_s]
current = current.next_node
end
list += [current.value.to_s]
length = list.length
return if length < value_to_reverse
counter = 1
(0..(length-1)).each do |value|
rotating_point = (length - 1) - value_to_reverse
if rotating_point and value > rotating_point
add_node(list[length - counter])
counter = counter + 1
else
add_node(list[value])
end
end
end
end
obj = Linkedlist.new(10)
obj.add_node(5)
obj.add_node(7)
obj.add_node(4)
obj.add_node(8)
obj.add_node(2)
obj.add_node(6)
obj.add_node(1)
obj.display
obj.reverse_link_list(5)
obj.display
This is my java code. It has a time complexity of O(n).
class Nodeq{
Nodeq next;
int data;
Nodeq(int x){
data=x;
}
}
public class LinkedListReverse {
Nodeq root;
public void print(){
Nodeq temp =root;
if(temp==null)
return;
while(temp!=null){
System.out.print(temp.data+" ");
temp=temp.next;
}
}
public void reverse(){
Nodeq fast=root,med=root;
Nodeq slow=root;
if(fast==null)
return;
for(int i=0;i<4;i++){
med=fast;
fast=fast.next;
if(fast==null){
System.out.println("Node are less than five");
return;
}
}
while(fast.next!=null){
slow=slow.next;
med=med.next;
fast=fast.next;
//System.out.println("In fast");
}
for(int i=0;i<2;i++){
int temp=slow.data;
slow.data=fast.data;
fast.data=temp;
fast=med;
slow=slow.next;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkedListReverse link=new LinkedListReverse();
link.root=new Nodeq(1);
link.root.next=new Nodeq(2);
link.root.next.next=new Nodeq(3);
link.root.next.next.next=new Nodeq(4);
link.root.next.next.next.next=new Nodeq(5);
link.root.next.next.next.next.next=new Nodeq(6);
link.root.next.next.next.next.next.next=new Nodeq(7);
link.root.next.next.next.next.next.next.next=new Nodeq(8);
link.root.next.next.next.next.next.next.next.next=new Nodeq(9);
link.print();
link.reverse();
System.out.println("Reversed link is : ");
link.print();
}
}
You can write a Reverse function of link list on node (default is head). algo:
1) Count linklist (O(n))
2) ReverseNumber = Count - 5
3) Move to ReverseNumber and set pointer suppose P1 (O(n-5) ==> O(n))
4) pass P1.next to reverse function (O(5) because only 5 to reverse)
5) P1.Next = Return of reverse function
So: Complexity = O(n)
Code:
- Rajesh Kumar December 09, 2014public SingleNode Reverse(SingleNode head) { if (head == null) return head; SingleNode curr = head; SingleNode prev = null; while(curr != null) { SingleNode next = curr.Next; curr.Next = prev; prev = curr; curr = next; } return prev; } static void Main(string[] arg) { SingleLinkList list = new SingleLinkList(); list.AddNodeAtLast(1); list.AddNodeAtLast(2); list.AddNodeAtLast(3); list.AddNodeAtLast(4); list.AddNodeAtLast(5); list.AddNodeAtLast(6); list.AddNodeAtLast(7); int count = list.Count; int ReverseNumber = 5; SingleNode reverseNode = new SingleNode(null); if (count <= ReverseNumber) { //If count less than 5 then reverse at head reverseNode = list.Reverse(list.Head); } else { int nodeToTravel = count - ReverseNumber; SingleNode startNode = list.Head; // Traverse to n-5 node for (int i = 0; i < nodeToTravel; i++) startNode = startNode.Next; //Reverse last 5 reverseNode = list.Reverse(startNode.Next); // link last 5 back to link list startNode.Next = reverseNode; // Print all link list data list.Print(list.Head); } }