PuzzlersWorld.com

  • Interview Questions
  • Interview Puzzles
  • Number Puzzles
  • Maths Puzzles

Linked List

Reverse a link list without using another

November 12, 2012 by asinghal 2 Comments

How to reverse a link list without using another link list?

Note: Linked list is singly linked list (there is only next pointer no previous pointer).
See Solution: Reverse a link list without using another linked listHide Solution

Take two pointers previous and current, increment both pointers by one till current reaches at the end of the list.
Reverse a Linked List

Reverse a Linked List

Node* reverse(Node* node)
{
	if(node == null)
		return null;
	Node * prev = node;
	Node* curr = node->next;
	
	while(curr != null){
		Node* tmp = curr->next;
		curr->next = prev;
		prev = curr;
		curr = temp;
	}
	return prev;
}

Filed Under: Interview Questions Tagged With: Interview, Linked List, medium

Detect if there is a cycle in a linked list

November 4, 2012 by asinghal 1 Comment

How can you find if a given linked list has a cycle in it?

Note: Linked list is singly linked list (there is only next pointer no previous pointer).
See Solution: Detect if there is a cycle in the linked listHide Solution

This can also be solved by using two pointers as we saw in Find nth element from end of linked list and Find middle element of linked list. Take two pointers pointer1 and pointer2, both pointing to head of the linked list initially, now increment pointer1 by one node and pointer2 by two nodes, If at any point of time pointer1 and pointer2 becomes equal then there is a cycle in the linked list, else pointer2 will reach end of the list and will become null eventually.

Code in C

bool isCyclePresent(Node* node){
	Node* pointer1 = node;
	Node* pointer2 = node;
	
	while(pointer2 != null && pointer2->next!=null){
		pointer1 = pointer1->next;
		pointer2 = pointer2->next->next;
		if(pointer1 == pointer2)
			return true;
	}
	return false;
}

Filed Under: Interview Questions Tagged With: Interview, Linked List, medium

Find nth element from end of linked list

November 4, 2012 by asinghal Leave a Comment

How to find nth element from the end of the linked list?

Or in other words Given an integer ‘n’, return a pointer to the n-th node from the end of the list.
Note: Linked list is singly linked list (there is only next pointer no previous pointer).

See Solution: find nth element from end of linked listHide Solution

Keep two pointers pointer1 and pointer2, both pointing to head of the linked list initially. Increment pointer1 by one node till it reaches (n+1)th node. Now increment both pointers by one node till pointer1 becomes null. At this point the node which pointer2 is pointing to will be the nth node from the last.

Code in C/C++

Node * getNthNodeFromLast(Node * node, int n){
	Node* pointer1 = node;
	Node* pointer2 = node;

	while(pointer1 != null && n > 0){
		pointer1 = pointer1->next;
		n--;
	}
	//List does not have n nodes, so return null
	if(n > 0)
		return null;
	//traverse till pointer1 becomes null
	while(pointer1 != null){
		pointer1 = pointer1->next;
		pointer2 = pointer2->next;
	}
	return pointer2;
}

Filed Under: Interview Questions Tagged With: Amazon Interview Questions, Easy, Linked List

Submit your Puzzle

You may also like

  • I am something that follows you wherever you go
  • Guess 30 marwadi names
  • Match kannada movies
  • Find the 9 letter word
  • One word with two meanings
  • Missing numbers in series
  • Number Puzzle #38
  • Guess the muhawaras from whatsapp emoticons
  • Complete the name of the sweets
  • Picture puzzle – Circle, dot and line

Get New Puzzles in your mailbox

Enter your email address and hit subscribe button.

Categories

  • Hacker Puzzle
  • WhatsApp Puzzles
  • Picture Puzzles
  • Riddles
    • Hindi Riddles
  • Bollywood Puzzles
  • Alphabetical Puzzles
  • Aive hi Puzzles
  • Interview Puzzles
  • Logical Puzzles
  • Interview Questions
    • Data Structures
    • Binary Tree
    • Algorithms
    • Recursion Questions
    • Amazon Interview Questions
    • Snapdeal Interview Questions
    • Google Code jam
  • Technical
  • Akbar and Birbal
  • Number Puzzles
  • Maths Puzzles
  • Miscellaneous

Hindi Puzzles

  • Hindi Puzzles
  • Number Puzzles in Hindi
  • SMS Puzzles in Hindi
  • WhatsApp Puzzles in Hindi

Favourites

  • Personalized Handmade Cards
  • Quotes & Wishes
  • Funny Jokes
  • Nice Stories
  • Hindi Stories

RSS Feeds

  • RSS - Posts

Social

  • View puzzlersworld’s profile on Twitter

Copyright © 2019 · Genius Fools on Genesis Framework · WordPress · Log in

  • Hacker Puzzle
  • WhatsApp Puzzles
  • Picture Puzzles
  • Riddles
    ▼
    • Hindi Riddles
  • Bollywood Puzzles
  • Alphabetical Puzzles
  • Aive hi Puzzles
  • Interview Puzzles
  • Logical Puzzles
  • Interview Questions
    ▼
    • Data Structures
    • Binary Tree
    • Algorithms
    • Recursion Questions
    • Amazon Interview Questions
    • Snapdeal Interview Questions
    • Google Code jam
  • Technical
  • Akbar and Birbal
  • Number Puzzles
  • Maths Puzzles
  • Miscellaneous