Tech Life On The Way

Given a linked list, swap every two adjacent nodes and return its head. For example, Given   1->2->3->4 , you should return the list as   2->1->4->3 . Your algorithm should use only constant space. You may   not   modify the values in the list, only nodes itself can be changed. /**  * Definition for singly-linked list.  * struct ListNode {  *     int val;  *     ListNode *next;  *     ListNode(int x) : val(x), next(NULL) {}  * };  */ class Solution { public :     ListNode* swap(ListNode * head ) {         ListNode *tmp = head ->next;         tmp->next = head ;         head ->next = nullptr ;         return tmp;     }  ...

/* Reverse a linked list from position   m   to   n . Do it in-place and in one-pass. For example: Given   1->2->3->4->5->NULL ,   m   = 2 and   n   = 4, return   1->4->3->2->5->NULL . Note: Given   m ,   n   satisfy the following condition: 1 ≤   m   ≤   n   ≤ length of list. */ struct ListNode {      int val;      ListNode *next;      ListNode( int x ) : val( x ), next( NULL ) {} }; ListNode *reverse( ListNode * head , int sz ) {        if ( sz == 1) return head ;        ListNode *tail;        if ( sz > 1) tail = head ;        ListNode *rlist = nullptr ;        while ( sz != 0) {      ...

/*** Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. http://leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html IDEA: 1) balanced BST should be started from the median O(nlogn) 2) construct in order, O(n) ***/ #include <iostream> using namespace std; struct node {        int val;        node *next;        node( int v ) {               this ->val = v ;               this ->next = nullptr ;        } }; struct tnode {        int val;        tnode *left, *right;        tnode( int v ) {    ...

/*** Given a node from a cyclic linked list which has been sorted, write a function to insert a value into the list such that it remains a cyclic sorted list. The given node can be any single node in the list. Pay attention on edge case. 1. input is nullptr 2. duplicate and single node http://leetcode.com/2011/08/insert-into-a-cyclic-sorted-list.html ***/ #include <iostream> using namespace std; struct node {        int val;        node *next;        node( int v ) {               this ->val = v ;               this ->next = nullptr ;        } }; void insert( node *& aNode , int x ) {        if ( aNode == nullptr ) {    ...