Doubly Linked List

Linked List/Queue/Stack Pending –
1. circular
2. round petrol problem
3. linked list and stack and queue mixed problem
4. cracking the coding interview problem
5. InterviewBit Problem Set

Make it a point to maintain a tail node in DLL and a size variable.

  1. ** Doubly Linked List
  2. **Reverse Doubly Linked List   Code
  3. *** Sort a linked list of 0,1 and 2’s –  count 0, 1 and 2’s.
    –  We can count the number of nodes having 0,1,2 and then make a new list with equal number of nodes.
    – We can do it on O(n) with no extra space. Code
  4. *** Stack and Doubly Linked List – Design a stack with operations on middle element. How to implement a stack which will support following operations in O(1) time complexity – push(), pop(), findMiddle(), deleteMiddle();
  5. ** Swap Kth node from beginning with Kth node from end in a Linked List – Algo –
    Let X be the kth node from beginning and Y be the kth node from end.
    Following are the interesting cases that must be handled.
    1) Y is next to X
    2) X is next to Y
    3) X and Y are same
    4) X and Y don’t exist (k is more than number of nodes in linked list)
  6. *** Design a stack with operations on middle element.
    How to implement a stack which will support following operations in O(1) time complexity? Link
    1) push() which adds an element to the top of stack.
    2) pop() which removes an element from top of stack.
    3) findMiddle() which will return middle element of the stack.
    4) deleteMiddle() which will delete the middle element.
    Implementing a stack using a Singly Linked List is pretty straightforward.  So what we do is to maintain a middlePointer(ok, that’s obvious) and have a flag which indicates when to move the middle pointer. We move the middle pointer when there was an element addition and the total node count became odd.
    When the list is empty middlePointer points to the first element. Now when the 3 node is added the middlePointer should be moved to it’s next.
    When an element is poped we may have to readjust the middlePointer. If there was even number of element, after pop it becomes odd, so now the middle needs to be moved back by one node. Since we need to move back to maintain the middlePointer in O(1) we will use a double linked list.
    C Code here is pretty clean
Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s