Placement Practice | Linked Lists

In this blog, we will discuss Linked Lists, but in this blog, we will discuss only major problems.


Linked Lists are linear or sequential data structures in which elements are stored at non-contiguous memory locations and are linked to each other using pointers.


We have already covered some topics like already



Reverse a Linked Lists

Problem: We have given a pointer to the head node of the Linked list, the task is to reverse the list. We need to reverse the list by changing the links between nodes. It can be interpreted as:

Input: Head of following linked list  
       1->2->3->4->NULL
Output: Linked list should be changed to,
       4->3->2->1->NULL

There can be three types of solutions to this problem, al of them are discussed here.


Three-Pointers Solution:

We will be using three-pointers prev, curr, and next to reverse the list. The below image is for only representative purposes.

Pseudo Code:

void reverse(Node* head) 
{
    // Initialize pointers 
    Node *curr = head; 
    Node *prev = NULL, *next = NULL
    while (curr != NULL) 
    {
        next = current->next
        current->next = prev
        prev = current
        current = next
    }
    head = prev 
}

Two Pointers Solution:

We will be using auxiliary two pointers curr and next to reverse the links of the linked list. This is a little bit tricky solution. Try out with examples-


Pseudo Code:

void reverse(Node* head) 
{
    // Initialize pointers 
    Node *current = head; 
    Node *prev = NULL, *next = NULL
    while (current != NULL) 
    {
        next = current->next
        current->next = prev
        prev = current
        current = next
    }
    head = prev 
}

Recursive Solution:

In this approach what we are trying to do is that we are making the previous node of the current node as his next node to reverse the linked list by passing a single pointer.

  1. We return the pointer of the next node to his previous(current) node and then make the previous node as the next node of the returned node and then returning the current node.

  2. We first traverse till the last node and making the last node as the head node of the reversed linked list and then applying the above procedure in a recursive manner.

Pseudo Code

Node* reverse(Node* node) 
{
    if (node == NULL) :
        return NULL
    if (node->next == NULL) :
        head = node
        return node
    Node* temp = reverse(node->next)
    temp->next = node 
    node->next = NULL 
    return node
}



Detect L

oop in a Linked List

Problem: We have to check whether a linked list has a loop or not.

The below diagram shows a linked list with a loop.

1 -> 2 -> 3
     |    |
     5 <- 4

Hashing Solution:

  • Traverse the list one by one and keep putting the node addresses in a Hash Table.

  • At any point, if NULL is reached then return false, and if next of current node points to any of the previously stored nodes in Hash then return true.

Pseudo Code:

bool detectLoop(Node* hs)
{
    seen //HashMap 
    while (hs != NULL) 
    {
        // If this node is already present
        // in hashmap it means there is a cycle
        if (seen.find(hs) == True)
            return true
        // If we are seeing the node for
        // the first time, insert it in hash
        seen.insert(hs)
        hs = hs->next
    }
    return false
}

Floyd’s Cycle-Finding Algorithm:

  • This is the fastest method.

  • Traverse linked list using two pointers.

  • Move one pointer by one step and another pointer by two-step.

  • If these pointers meet at the same node then there is a loop.

  • If pointers do not meet then the linked list doesn’t have a loop.

Pseudo Code:

bool detectloop(Node* head) 
{
    Node *slow = head, *fast = head
  
    while (slow && fast && fast->next) 
    {
        slow = slow->next
        fast = fast->next->next
        if (slow == fast) 
            return true 
    }
    return false  
}  
Find Intersection Point of Two Linked List

Problem: By some programming error, the end node of one linked list got linked to the second linked list, depicted below. Write a program to get the point where two of them merge.

A:          a1 -> a2
                    ->
                      c1 -> c2 -> c3
                    ->           
B:     b1 -> b2 -> b3

The above diagram shows an example with two linked lists having 100 as an intersection point.


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int len1 = 0;
        int len2 = 0;
        ListNode p1=headA, p2=headB;
        if (p1 == null || p2 == null)
            return null;
 
        while(p1 != null){
            len1++;
            p1 = p1.next;
        }
        while(p2 !=null){
            len2++;
            p2 = p2.next;
        }
        int diff = 0;
        p1=headA;
        p2=headB;
 
        if(len1 > len2){
            diff = len1-len2;
            int i=0;
            while(i<diff){
                p1 = p1.next;
                i++;
            }
        }else{
            diff = len2-len1;
            int i=0;
            while(i<diff){
                p2 = p2.next;
                i++;
            }
        }
        while(p1 != null && p2 != null){
            if(p1.val == p2.val){
                return p1;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return null;
    }
}

This solution works in O(m+n) but requires additional information with each node. An alternative solution that doesn’t require modification to the basic data structure can be implemented using a hash. Traverse the first linked list and store the addresses of visited nodes in a hash. Now traverse the second linked list and if you see an address that already exists in the hash then return the intersecting node.




Happy Coding!

Follow us on Instagram @programmersdoor

Join us on Telegram @programmersdoor


Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem.

Follow Programmers Door for more.

#blog #interview #placement #learn #computer #science

        Contact Us

programmersdoor@gmail.com

  • LinkedIn
  • Facebook
  • Instagram

©2023 by Programmers Door