Monday, September 26, 2011

Deleting a node in singly linked list if it is less than any of the successor nodes

Question : Given a link list of integers delete all nodes which have value smaller than the value of any following node.
Example :7 4 5 2 3 6
Output :  7 6

Solution:
The solution is to :
1. Reverse the list
6 3 2 5 4 7
2. Delete all the elements which are below the max-till-now element.
eg. max-till-now=6....Delete all the elements below 6...till you find another max element = max-till-now = 7
6 7
3. Reverse the left out list again
7 6




2 comments:

  1. Hi,
    try with 1,7,0,10.
    output must be 10.
    but your algorithm outputs wrong answer

    ReplyDelete
  2. it seems that algo is correct..
    1,7,0,10
    reverse

    10 0 7 1

    max_till_here= 10

    0 < 10 delete 0

    left : 10 7 1

    7 < 10 : delete 7

    1 < 10 : delete 1

    output : 10

    ReplyDelete