CareerCup

public void ReverseNFromFrontToNFromBack(int n)
        {
            Node p0 = null, p1 = null, p2 = head, p3 = head;
            while (n > 1)
            {
                p0 = p3;
                p3 = p3.next;
                n--;
            }
            p1 = p3;
            while (p3.next != null)
            {
                p2 = p2.next;
                p3 = p3.next;
            }
            
            //now p1 & p2 points to start and end of sub-list which needs to be reversed 
            ReverseMiddle(p0, p1, p2);
        }

        private void ReverseMiddle(Node prev, Node curr, Node next)
        {
            Node head = prev;
            Node b = curr;
            Node last = next.next;
            while(curr != last)
            {
                next = curr.next;
                curr.next = prev;
                prev = curr;
                curr = next;
            }
            b.next = last;
            head.next = prev;
        }

struct ListNode
{
int data;
ListNode* next;
};

ListNode* reverse_list(ListNode* source_list)
{
if(source_list->next == nullptr)
{
return source_list;
}
ListNode* reversed = reverse_list(source_list->next);
reversed->next = source_list;
source_list->next = nullptr;
return reversed;
}

ListNode* last_elem_in_list(ListNode* source_list)
{
ListNode* runner = source_list;
while(runner->next != nullptr)
runner = runner->next;
}

ListNode* reverse_middle(ListNode* source_list, int n)
{
n -= 1;
if(n <= 0)
return source_list;

ListNode* last_not_reversed_runner = source_list;
for(int i = 0; i < n - 1; i++)
{
if(last_not_reversed_runner->next == nullptr)
return source_list;
last_not_reversed_runner = last_not_reversed_runner->next;
}

// Now runner points on the last not reversed elem

ListNode* last_elem_runner = source_list;
ListNode* fin_runner = last_not_reversed_runner;

bool found = false;

while(fin_runner->next != nullptr)
{
fin_runner = fin_runner->next;
if(last_elem_runner == last_not_reversed_runner)
found = true; // We have at least 2n elems
last_elem_runner = last_elem_runner->next;
}
if(!found || last_elem_runner == last_not_reversed_runner->next)
return source_list;

// Now we know that we have to reverse at least 2 elements;

ListNode * first_not_reversed = last_elem_runner->next;

last_elem_runner->next = nullptr;

last_not_reversed_runner->next = reverse_list(last_not_reversed_runner->next);
last_elem_in_list(last_not_reversed_runner->next)->next = first_not_reversed;

return source_list;
}

int EvaluateExpr(const std::string &postfix)
{
    if (postfix.size()<1)
        return 0;
    std::array<char,4> oper={'+','-','*','/'};
    std::stack<int> result;
    for(auto ch:postfix)
    {
        
        auto ret= std::find_if(oper.cbegin(),oper.cend(),[ch](char ch1){ if (ch== ch1) return true;return false;});
        if ( ret != oper.cend()) // so we find the operator
        {
            auto val1 = result.top();result.pop();
            auto val2 = result.top();result.pop();
            switch (ch)
            {
            case '+':result.push(val1+val2);
                break;
            case '-':result.push(val1-val2);
                break;
            case '*':result.push(val1*val2);
                break;
            case '%':result.push(val1/val2);
                break;
            default:
                break;
            }
        }
        else
        {
            int val = ch-'0';
            result.push(val);
        }
    }
    
    return result.top();
}

public void riverse(int n)
node ptr=start;;
pos=n;//n is number given
for(int i=1;i<=size;i++)
{
  if(i==pos)
   {
    k=i;
    break;
   }
ptr=ptr.getlink();
}
firstprev=ptr;
first=ptr.getlink();
int i=1;
while(ptr!=null&&i<=n)
{
ptr=ptr.getlink();
}
if(ptr==null)
{
last=end;
}
else
{
last=ptr;
}
last_next=ptr.getlnik();
i=1;
ne=first;
do{
next=ne.getlink();
nnext=next.getlink();
next.setlink(ne);
next=nnext;
ne=next;
i++;
}while(next!=null&&i!=n)
firstprev.setlink(last);
first.setlink(lastnext);
}

public void riverse(int n)
{
for(i=1;i<=size;i++)
{
 if(i==n)
   break;
ptr=ptr.getlink();
}
firstprev=ptr;
first=ptr.getlink();
i=1;
while(ptr!=null&&i<=n)
{
ptr=ptr.getlink();
}
if(ptr==null)
   last=end;
   lastnext=null;
else
  last=ptr;
  lastnext=ptr.getlink();
i=1;
n=first;
do{
next=ne.getlink();
nnext=next.getlink();
next.setlink(ne);
next=nnext;
n=next;
}
firstprev.setlink(last);
first.setlink(lastnext);
}

void ReverseOrder(Node*& p, int n)
{
	Node* pfast = p, *prevLast = NULL;
	int count = 0;
	for (int i = 0; i < n-1 && pfast != NULL; i++) //Move n-1 ahead , pFast will then be in nth node
	{
		prevLast = pfast;
		pfast = pfast->next;
		count++;
	}
	Node* start = pfast;  //Store start pos, nth node from start
	while (pfast != NULL)
	{
		pfast = pfast->next;
		count++;
	}
	if (n > count) return;
	
	Node *curr = start, *prev = NULL, *next = NULL;

	for (int i = 0; i != count-2*n+2 && curr!=NULL ;i++)
	{
		next = curr->next;
		curr->next = prev;
		prev = curr;
		curr = next;
	}
	prevLast->next = prev;
	start->next = curr;
}

public static void ReverseListN2N(List<int> originalList, int n)
{
int start = n - 1;
int end = originalList.Count - n;
int temp;
while (start < end)
{
temp = originalList[start];
originalList[start] = originalList[end];
originalList[end] = temp;
start++;
end--;
}
}

public static void ReverseListN2N(List<int> originalList, int n)
        {
            int start = n - 1;
            int end = originalList.Count - n;
            int temp;
            while (start < end)
            {
                temp = originalList[start];
                originalList[start] = originalList[end];
                originalList[end] = temp;
                start++;
                end--;
            }
        }

[TestMethod]
public void ReverseListN2N_Test()
{
List<int> list = new List<int>() { 1, 2, 3, 4, 5 };
ReverseList.ReverseListN2N(list, 2);

List<int> target = new List<int>() { 1, 4, 3, 2, 5 };
Assert.AreEqual(true, list.SequenceEqual(target));
}