LinkedList Standard Questions
4 min readNov 8, 2022
GeeksForGeeks + LeetCode
Q1. Find Middle of a LinkedList
class Solution
{
int getMiddle(Node head)
{
if(head==null) return -1; Node fast = head;
Node slow = head; while(fast != null && fast.next != null)
{ fast = fast.next.next;
slow = slow.next; } return slow.data;
}
}
Q2. Delete Middle of a LinkedList
class Solution {
Node deleteMid(Node head) {
if(head == null || head.next == null)
{
return null;
}
Node slow = head;
Node fast = head;
Node pre = null;
while(fast != null && fast.next != null){
pre = slow;
slow = slow.next;
fast = fast.next.next;
}
pre.next = slow.next;
return head;
}
}Q3. Remote duplicate elements from Sorted LinkedList
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode temp = head;
while(temp != null){
if (temp.next == null)
{
break;
}
if(temp.val == temp.next.val)
{
temp.next = temp.next.next; }else
{
temp = temp.next;
}
} return head;
}
}
Q4. Add 1 to a number represented as LinkedList
SKIP FOR NOWQ5. Reverse a LinkedList in Groups of given size
SKIP FOR NOWQ6. Detect loop in a LinkedList
// SOLUTION-1 (Using Set)class Solution {
public static boolean detectLoop(Node head){
Node temp = head;
Set<Node> set = new HashSet<>();
while(temp != null){
if(set.contains(temp))
{
return true;
}
set.add(temp);
temp = temp.next;
}
return false;
}
}// SOLUTION-2 (Using Two Pointers)class Solution {
public static boolean detectLoop(Node head){
Node slow = head;
Node fast = head;
while(fast != null && fast.next != null)
{
slow = slow.next;
fast = fast.next.next;
if(slow == fast) return true;
}
return false;
}
}
Q7. Remove Loop in LinkedList
NOT SUREQ8. Find nth node from the end of LinkedList
class GfG
{
public static int length(Node head){
int length = 0;
while(head != null){
length++;
head = head.next;
}
return length;
}
int getNthFromLast(Node head, int n)
{
int len = length(head);
if(len < n) return -1;
for(int i = 0; i < len-n; i++){
head = head.next;
}
return head.data;
}
}Q9. Function to check if a singly linked list is a palindrome
class Solution {
public static ListNode reverse(ListNode head){
ListNode temp = head;
ListNode prev = null;
ListNode next = head;
while(temp != null){
next = temp.next;
temp.next = prev;
prev = temp;
temp = next;
}
return prev;
}
public static ListNode mid(ListNode head){
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
public boolean isPalindrome(ListNode head) {
if(head.next == null || head == null){
return true;
}
if(head.next.next == null){
if(head.val != head.next.val){
return false;
}else{
return true;
}
}
ListNode mid = mid(head);
ListNode nr = reverse(mid);
ListNode temp = head;
while(nr != null){
if(temp.val != nr.val){
return false;
}
temp = temp.next;
nr = nr.next;
}
return true;
}
}Q10. Merge a linked list into another linked list at alternate positions
SKIPQ11. Remove nth node from the end of LinkedList
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode slow = head;
ListNode fast = head;
for(int i = 0; i < n; i++){
fast = fast.next;
}
if(fast == null) return head.next;
while(fast.next != null){
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return head;
}
}Q12. Rotate a LinkedList
class Solution {public static int length(ListNode head){ ListNode temp = head;
int length = 0; while(temp != null){
length++;
temp = temp.next;
} return length;
}
public ListNode rotateRight(ListNode head, int k) {if(head == null || head.next == null || k == 0) return head; int len = length(head); ListNode temp = head; while(temp.next != null)
{
temp = temp.next;
} temp.next = head;
k = k%len;
k = len - k;
for(int i = 0; i < k; i++)
{
temp = temp.next;
} head = temp.next;
temp.next = null; return head;
}
}
Q13. Delete last occurrence of an item from LinkedList
static Node deleteLast(Node head, int key)
{
Node x = null;
Node temp = head;
while (temp != null)
{
if (temp.key == key)
x = temp;
temp = temp.next;
}
if (x != null)
{
x.key = x.next.key;
temp = x.next;
x.next = x.next.next;
}
return head;
}Q14. Write a function to delete a LinkedList
class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}Q15. Reverse a LinkedList
class Solution {
public ListNode reverseList(ListNode head) {
ListNode temp = head;
ListNode prev = null;
ListNode next = head;
while(temp != null){
next = temp.next;
temp.next = prev;
prev = temp;
temp = next;
}
return prev;
}
}Q16. Merge 2 Sorted LinkedLists
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(0);
ListNode temp = dummy;
while(list1 != null && list2 != null){
if(list1.val < list2.val){
temp.next = list1;
list1 = list1.next;
} else if(list1.val >= list2.val){
temp.next = list2;
list2 = list2.next;
}
temp = temp.next;
}
if(list1 == null) temp.next = list2;
if(list2 == null) temp.next = list1;
return dummy.next;
}
}Q17. Intersection of 2 LinkedLists
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p1 = headA;
ListNode p2 = headB;
if(p1 == null && p2 == null) return null;
while(p1 != null && p2 != null && p1 != p2){
p1 = p1.next;
p2 = p2.next;
if(p1==p2) return p1;
if(p1 == null) {
p1 = headB;
}
if(p2 == null){
p2 = headA;
}
}
return p1;
}
}Q18. Odd Even LinkedList
class Solution {
public ListNode oddEvenList(ListNode head) {
if(head == null) return null;
ListNode odd = head;
ListNode even = head.next;
ListNode evenHead = even;
while(even != null && even.next != null){
odd.next = odd.next.next;
even.next = even.next.next;
odd = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
}
