Linked List

Questions On Linked List

Problem 1: Remove duplicates from an unsorted Linked List.
The simplest solution of this problem is- run two loops for the items – select each item and search through the list.

This solution is not very time efficient. It will take O(n2) time. We can do it in O(n) time using java.util.Set. Set doesn’t allow duplicates and we know that Set add method return false if Set already have the added element.Add list element to Set, if it return false while adding change the previous pointer next to the current next.

Problem 2: Write code to create a sorted list.
To create a sorted list, you will have to take care while inserting the element. The new element should be inserted at right position such that all its predecessor are smaller and all its successor are greater.

Problem 3: Display a Singly Linked List in reverse order.
You can easily display a list in reverse using Stack.

Problem 4: Implement an algorithm to find the Kth to last element of a Singly Linked List.
There are recursive solution also for this problem but I will find the iterative one easy. In iterative solution we maintain two pointers let say P1 and P2. Point P1 to the first element and move P2 to the Kth node. Now start moving P1 and P2 to the next node until P2 reaches to the end. Please note that P1 is running K node behind P2 therefore when P2 will reach to the end P1 will be at Kth node from the last.

Problem 5: Write a program to reverse a Singly Linked List.

Problem 6: Write a program to find whether two list interest or not?

Problem 7: Copy a linked list with next and arbitrary pointer.
There is a Doubly Linked List given with one pointer of each node pointing to the next node as in a singly linked list. The second pointer is an arbitrary pointer and can point to any node in the list and not just the previous node. Write a program in O(n) time to copy this list.
Linked-List-Arbit-ptr

To create a copy of the List:

  • First create a copy of all nodes with next pointer as it is in original list.
  • Point next pointer of each node of the original list to the corresponding node of the copy list.
  • Point the arbitrary pointer of each node of the copy list to the corresponding node in the original list.
  • Linked-List-Arbit-ptr1

  • Construct the copy list as below.
  • copyListNode->arbitPtr = copyListNode->arbitPtr->arbitPtr->next;
    copyListNode = copyListNode->next;

Java Implementation

First create a Node class with next and arbitrary pointer.

References:

  • Introduction To Algorithm – CLRS.
  • Data Structures and Algorithms in Java – Adam Drozdek
  • Data Structure & Algorithms In Java – Robert Lafore
  • Cracking The Coding Interview- Gayle Laakmann McDowell
  • Programming Interviews Exposed- John Mongan, Eric Giguère, Noah Kindler.
  • Coding Interviews- Harry He

  • kundan dwivedi

    Nice Write up Kunal…keep it up