Linked List

Problem solving techniques in Linked List

Detecting a Cycle in a Linked List:

Floyd’s Cycle Finding Algorithm or Hare Tortoise Algorithm

• The idea is to use two pointers, one called the “fast” pointer and the other called the “slow” pointer. The fast pointer moves two steps ahead of the slow pointer at each iteration, while the slow pointer moves only one step.
• This allows us to traverse the linked list in half the time, as compared to a single pointer traversal.
• Also known as the Fast and Slow pointer concept.
• It is used in detecting a loop in a linked list.

Time complexity: O(N),Auxiliary Space: O(1).

While Traversing the linked list two things will occur:

1. The Fast pointer may reach the end (NULL) this shows that there is no loop in the linked list.
2. The Fast pointer again catches the slow pointer at some time therefore a loop exists in the linked list.

Source

There is a Node class to which the nodes of linked list belong; hence we create the objects of class Node.Head points of the first node of the linked list.

// create two references at the start of LinkedList.
 //first initialize slow and fast pointers to the head of the linked list.  
    Boolean flag=false;
    Node fast = head;
    Node slow = head;

    while(fast != null && fast.next !=null) {

      // move fast reference by 2 nodes
      fast = fast.next.next;

      // move slow reference by 1 node
      slow = slow.next;

      // if two references meet
      // then there is a loop
      if(fast == slow) {
        flag=true;
        break;
      }
    }
   if(flag==true){
      System.out.println(“Cycle present in the linked list”);}
   else{
      System.out.println(“Cycle not present in the linked list”);}

Reversing of the Linked List:

Iterative Method

Approach:

1. initialize three pointers prev as NULL, curr as head, and next as NULL.
2. Iterate through the linked list. In a loop, do the following:
3. Before changing the next of curr, store the next node

next = curr -> next

4. Now update the next pointer of curr to the prev

curr -> next = prev

5. Update prev as curr and curr as next

prev = curr

curr = next

Time Complexity: O(N), Auxiliary Space: O(1)

Java Code:

There is a Node class to which the nodes of linked list belong; hence we create the objects of class Node.Head points of the first node of the linked list.

Node prev = null;
Node current = Head;
Node next=null;
while(current!=null){
   next=current.next;
   current.next=prev;
   prev=current;
   current=next;
}
Head=prev; //returning the reversed linked list

Intersection of 2 Linked Lists:

Approach:

1. Get the count of the nodes in the first list, let the count be c1.
2. Get the count of the nodes in the second list, let the count be c2.
3. Get the difference of counts d = abs(c1 — c2)
4. Now traverse the bigger list from the first node to d nodes so that from here onwards both the lists have an equal no of nodes
5. Then we can traverse both lists in parallel till we come across a common node. (Note that getting a common node is done by comparing the address of the nodes)
6. Time Complexity: O(m+n),Auxiliary Space: O(1)

Source

//Method to get number of nodes present in the linked list
int getCount(Node node)
    {
        Node current = node;
        int count = 0;
  
        while (current != null) {
            count++;
            current = current.next;
        }
  
        return count;
    }
/* function to get the intersection point of two linked
   lists head1 and head2 where head1 has d more nodes than head2 */
    int _getIntesectionNode(int d, Node node1, Node node2)
    {
        int i;
        Node current1 = node1;
        Node current2 = node2;
        for (i = 0; i < d; i++) {
            if (current1 == null) {
                return -1;
            }
            current1 = current1.next;
        }
        while (current1 != null && current2 != null) {
            if (current1.data == current2.data) {
                return current1.data;
            }
            current1 = current1.next;
            current2 = current2.next;
        }
  
        return -1;
    }

int getNode()
    {
        int c1 = getCount(head1);
        int c2 = getCount(head2);
        int d;
  
        if (c1 > c2) {
            d = c1 - c2;
            return _getIntesectionNode(d, head1, head2);
        }
        else {
            d = c2 - c1;
            return _getIntesectionNode(d, head2, head1);
        }
    }

For queries regarding the content, please drop a mail to loop@cumminscollege.in Links for in-depth studying and practice problems are sent via mail to students of the college on the date of publishing of the blog by Loop Club. The content is a part of DSA Bulletins started by Team Loop, to provide thorough knowledge and facilitate the learning of new topics of DSA. We are a group of students who are passionate about CP and DSA and want to create awareness and help students in the above topics.