Scribd Logo
Upload

Welcome to Scribd!

  • 12 views

    Linked Lists

    Uploaded by

    shubhammmprajapati95

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Linked Lists

    Uploaded by

    shubhammmprajapati95
    12 views9 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    12 views9 pages

    Linked Lists

    Uploaded by

    shubhammmprajapati95

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 9

    Q1: Check if an Element is Present in a Linked List

    Problem: Given a linked list and a key `X`, check if `X` is present in the linked list or not.

    Solution:
    class Node {
    int data;
    Node next;

    Node(int data) {
    this.data = data;
    this.next = null;
    }
    }

    public class LinkedListSearch {


    // Function to check if an element is present in the linked list
    public static boolean searchElement(Node head, int key) {
    // Traverse the linked list
    while (head != null) {
    // If the current node's data is equal to the key, return true
    if (head.data == key) {
    return true;
    }
    head = head.next;
    }
    // If the key is not found, return false
    return false;
    }

    public static void main(String[] args) {


    // Creating a linked list: 14 -> 21 -> 11 -> 30 -> 10
    Node head = new Node(14);
    head.next = new Node(21);
    head.next.next = new Node(11);
    head.next.next.next = new Node(30);
    head.next.next.next.next = new Node(10);

    int X1 = 14;
    int X2 = 13;

    System.out.println(searchElement(head, X1) ? "Yes" : "No"); // Output: Yes


    System.out.println(searchElement(head, X2) ? "Yes" : "No"); // Output: No
    }
    }

    Q2: Insert a Node at a Given Position in a Linked List

    Problem: Insert a node at the given position in a linked list. We are given a pointer to a node,
    and the new node is inserted after the given node.

    Solution:

    class LinkedListInsertion {
    // Function to insert a new node after a given node
    public static void insertAfter(Node prevNode, int newData) {
    // Check if the previous node is null
    if (prevNode == null) {
    System.out.println("The given previous node cannot be null.");
    return;
    }

    // Create the new node and put data in it


    Node newNode = new Node(newData);
    // Make the next of the new node as next of previous node
    newNode.next = prevNode.next;
    // Make the next of previous node as new node
    prevNode.next = newNode;
    }

    public static void printList(Node head) {


    Node current = head;
    while (current != null) {
    System.out.print(current.data + " ");
    current = current.next;
    }
    System.out.println();
    }

    public static void main(String[] args) {


    // Creating a linked list: 1 -> 2 -> 4 -> 5 -> 6
    Node head = new Node(1);
    head.next = new Node(2);
    head.next.next = new Node(4);
    head.next.next.next = new Node(5);
    head.next.next.next.next = new Node(6);
    // Pointer to the node with value 2 and new value to be inserted is 3
    Node pointer = head.next; // Node with value 2
    int value = 3;

    // Insert the new node


    insertAfter(pointer, value);

    // Print the updated list: 1 -> 2 -> 3 -> 4 -> 5 -> 6


    printList(head); // Output: 1 2 3 4 5 6
    }
    }

    Q3: Delete All Duplicates in a Sorted Linked List

    Problem: Given the head of a sorted linked list, delete all duplicates such that each element
    appears only once. Return the linked list sorted as well.

    Solution:

    class LinkedListRemoveDuplicates {
    // Function to remove duplicates from a sorted linked list
    public static Node removeDuplicates(Node head) {
    Node current = head;

    // Traverse the linked list


    while (current != null && current.next != null) {
    // If current node's data is the same as the next node's data
    if (current.data == current.next.data) {
    // Skip the next node
    current.next = current.next.next;
    } else {
    // Move to the next node
    current = current.next;
    }
    }
    return head;
    }

    public static void printList(Node head) {


    Node current = head;
    while (current != null) {
    System.out.print(current.data + " ");
    current = current.next;
    }
    System.out.println();
    }

    public static void main(String[] args) {


    // Creating a sorted linked list: 1 -> 2 -> 2 -> 3 -> 4 -> 4 -> 5
    Node head = new Node(1);
    head.next = new Node(2);
    head.next.next = new Node(2);
    head.next.next.next = new Node(3);
    head.next.next.next.next = new Node(4);
    head.next.next.next.next.next = new Node(4);
    head.next.next.next.next.next.next = new Node(5);

    // Remove duplicates
    head = removeDuplicates(head);

    // Print the updated list: 1 -> 2 -> 3 -> 4 -> 5


    printList(head); // Output: 1 2 3 4 5
    }
    }

    Q4: Check if a Linked List is a Palindrome

    Problem: Given the head of a singly linked list, return `true` if it is a palindrome or `false`
    otherwise.

    Solution:

    import java.util.Stack;

    class LinkedListPalindrome {
    // Function to check if a linked list is a palindrome
    public static boolean isPalindrome(Node head) {
    Stack<Integer> stack = new Stack<>();
    Node current = head;

    // Push all elements of the list to the stack


    while (current != null) {
    stack.push(current.data);
    current = current.next;
    }
    // Reinitialize the current pointer to the head
    current = head;
    // Compare elements of the list with the elements in the stack
    while (current != null) {
    if (current.data != stack.pop()) {
    return false; // If any element is not the same, it is not a palindrome
    }
    current = current.next;
    }

    return true; // If all elements are the same, it is a palindrome


    }

    public static void main(String[] args) {


    // Creating a linked list: 1 -> 2 -> 2 -> 1
    Node head = new Node(1);
    head.next = new Node(2);
    head.next.next = new Node(2);
    head.next.next.next = new Node(1);

    // Check if the linked list is a palindrome


    System.out.println(isPalindrome(head)); // Output: true
    }
    }

    Q4. Given the head of a singly linked list, return true if it is a palindrome or false otherwise.
    class Node {
    int data;
    Node next;

    Node(int data) {
    this.data = data;
    this.next = null;
    }
    }

    public class LinkedListPalindromeCheck {

    // Function to check if a linked list is a palindrome


    public static boolean isPalindrome(Node head) {
    if (head == null || head.next == null) {
    return true;
    }
    // Step 1: Find the middle of the linked list
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    }

    // Step 2: Reverse the second half of the linked list


    Node secondHalf = reverseList(slow);

    // Step 3: Compare the first half with the reversed second half
    Node firstHalf = head;
    while (secondHalf != null) {
    if (firstHalf.data != secondHalf.data) {
    return false;
    }
    firstHalf = firstHalf.next;
    secondHalf = secondHalf.next;
    }

    return true;
    }

    // Function to reverse a linked list


    public static Node reverseList(Node head) {
    Node prev = null;
    Node current = head;
    while (current != null) {
    Node next = current.next;
    current.next = prev;
    prev = current;
    current = next;
    }
    return prev;
    }

    public static void main(String[] args) {


    // Example 1: Input: 1 -> 2 -> 2 -> 1, Output: true
    Node head1 = new Node(1);
    head1.next = new Node(2);
    head1.next.next = new Node(2);
    head1.next.next.next = new Node(1);
    System.out.println(isPalindrome(head1)); // Output: true
    // Example 2: Input: 1 -> 2, Output: false
    Node head2 = new Node(1);
    head2.next = new Node(2);
    System.out.println(isPalindrome(head2)); // Output: false
    }
    }

    Q5. Given two numbers represented by two lists, write a function that returns the sum list. The
    sum list is a list representation of the addition of two input numbers.

    class Node {
    int data;
    Node next;

    Node(int data) {
    this.data = data;
    this.next = null;
    }
    }

    public class LinkedListSum {

    // Function to add two numbers represented by linked lists


    public static Node addTwoLists(Node l1, Node l2) {
    Node dummyHead = new Node(0);
    Node current = dummyHead;
    int carry = 0;

    // Traverse both linked lists


    while (l1 != null || l2 != null) {
    int x = (l1 != null) ? l1.data : 0;
    int y = (l2 != null) ? l2.data : 0;
    int sum = carry + x + y;

    // Update carry for the next calculation


    carry = sum / 10;
    // Create a new node with the sum of the current digits
    current.next = new Node(sum % 10);
    current = current.next;

    // Move to the next nodes in both linked lists


    if (l1 != null) l1 = l1.next;
    if (l2 != null) l2 = l2.next;
    }

    // If there is still a carry left, add a new node with the carry
    if (carry > 0) {
    current.next = new Node(carry);
    }

    return dummyHead.next;
    }

    // Function to print the linked list


    public static void printList(Node head) {
    Node current = head;
    while (current != null) {
    System.out.print(current.data + " ");
    current = current.next;
    }
    System.out.println();
    }

    public static void main(String[] args) {


    // Example 1: Input: List1: 5->6->3, List2: 8->4->2
    Node list1 = new Node(5);
    list1.next = new Node(6);
    list1.next.next = new Node(3);

    Node list2 = new Node(8);


    list2.next = new Node(4);
    list2.next.next = new Node(2);

    Node result = addTwoLists(list1, list2);


    System.out.print("Resultant list: ");
    printList(result); // Output: 1->4->0->5

    // Example 2: Input: List1: 7->5->9->4->6, List2: 8->4


    Node list3 = new Node(7);
    list3.next = new Node(5);
    list3.next.next = new Node(9);
    list3.next.next.next = new Node(4);
    list3.next.next.next.next = new Node(6);

    Node list4 = new Node(8);


    list4.next = new Node(4);
    Node result2 = addTwoLists(list3, list4);
    System.out.print("Resultant list: ");
    printList(result2); // Output: 7->6->0->3->0
    }
    }

    You might also like