LeetCode: Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
   typedef ListNode ln;  
   
   ListNode *removeNthFromEnd(ListNode *head, int n) {  
     ln *dummy = new ln(0);  
     dummy->next = head;  
     ln *fast = dummy, *slow = dummy;  
     while(n--)  
     {  
       fast = fast->next;  
     }  
       
     while(fast->next)  
     {  
       fast = fast->next;  
       slow = slow->next;  
     }  
       
     slow->next = slow->next->next;  
       
     return dummy->next;  
   }  

LeetCode: Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
   typedef ListNode ln;  
   
   ListNode *partition(ListNode *head, int x) {  
     ln *list1 = new ln(0);  
     ln *list2 = new ln(0);  
       
     ln *tmp = head, *newHead = NULL, *list2head = list2;  
     while(tmp)  
     {  
       if (tmp->val < x)  
       {  
         list1->next = tmp;  
         list1 = tmp;  
         if(!newHead) newHead = tmp;  
       }  
       else  
       {  
         list2->next = tmp;  
         list2 = tmp;  
       }  
       tmp = tmp->next;  
     }  
     if(!newHead) newHead = list2head->next;  
     list1->next = list2head->next;  
     list2->next = NULL;  
   
     return newHead;  
   }  

LeetCode: Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
    
   typedef ListNode ln;  
   
   int count(ln *head)  
   {  
     int cnt = 0;  
     while(head){  
       head = head->next;  
       cnt++;  
     }  
     return cnt;  
   }  
   
   ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {  
     if(l1 == NULL && l2 == NULL)return NULL;  
     if(l1 == NULL)return l2;  
     if(l2 == NULL)return l1;  
   
     ln *head = NULL,*last;  
     int sum = 0, carry = 0;  
   
     while(l1 && l2)  
     {  
       sum = l1->val + l2->val + carry;  
       carry = sum/10;  
       sum = sum%10;  
       ln *n = new ln(sum);  
       if(!head){head = n; last = head;}  
       else  
       {  
         last->next = n;  
         last = n;  
       }  
   
       l1 = l1->next;  
       l2 = l2->next;  
     }  
   
     while(l1)  
     {  
       sum = l1->val + carry;  
       carry = sum/10;  
       last->next = new ln(sum%10);  
       l1 = l1->next;  
       last = last->next;  
     }  
   
     while(l2)  
     {  
       sum = l2->val + carry;  
       carry = sum/10;  
       last->next = new ln(sum%10);  
       l2 = l2->next;  
       last = last->next;  
     }  
   
     if (carry)last->next = new ln(carry);  
   
     return head;  
   }  

LeetCode: Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
   
   #define tr(c,it) for(decltype((c).begin()) (it) = (c).begin(); (it) != (c).end(); (it)++)  
    
   typedef ListNode ln;   
   
   struct compare{  
     bool operator() (ListNode *a, ListNode *b) const  
     {  
       return (a->val > b->val);  
     }  
   };  
   
   ListNode *mergeKLists(vector<ListNode *> &lists) {  
     int n = lists.size();  
     if(n<1)return NULL;  
     vector<ListNode *> Cur;  
     ListNode *head = NULL, *last = NULL;  
     priority_queue<ListNode *,vector<ListNode *>, compare > pq;  
     tr(lists,it)  
     {  
       int i = it - lists.begin();  
       Cur.push_back(*it);  
       if(*it)  
         pq.push(*it);  
     }  
     while(!pq.empty())  
     {  
       ln *min = pq.top();  
       pq.pop();  
       if(!head)  
       {  
         head = min;  
         last = min;  
       }  
       else  
       {  
         last->next = min;  
         last = min;  
       }  
       if(last->next)  
         pq.push(last->next);  
     }  
     return head;  
   }  

LeetCode: Swap Nodes in Pairs

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) {}  
  * };  
  */  
   
   ListNode *swapPairs(ListNode *head) {  
     if(!head || !head->next)return head;  
     ListNode *nxt=head->next, *cur = head, *prev = NULL;  
     ListNode *res = head->next;  
     while(cur && nxt)  
     {  
       cur->next = nxt->next;  
       nxt->next = cur;  
       if(prev)  
         prev->next = nxt;  
       prev = cur;  
       cur = cur->next;  
         
       if(cur)nxt = cur->next;  
     }  
     return res;  
   }  

LeetCode: Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  

   ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {  
     if(l1 == NULL)return l2;  
     if(l2 == NULL)return l1;  
     ListNode *newHead = l1->val<=l2->val?l1:l2;  
     if(l1->val <= l2->val)  
     {  
       l1->next = mergeTwoLists(l1->next,l2);  
     }  
     else  
     {  
       l2->next = mergeTwoLists(l2->next, l1);  
     }  
     return newHead;  
   }  

LeetCode: Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  

   ListNode *deleteDuplicates(ListNode *head) {  
     if(!head || !head->next)return head;  
     ListNode *prev = head, *cur = head->next;  
     while(cur)  
     {  
       while(cur && cur->val == prev->val)  
       {  
         prev->next = cur->next;  
         ListNode *tmp = cur;  
         cur = cur->next;  
         delete tmp;  
       }  
       if (cur)  
       {  
         prev = cur;  
         cur = cur->next;  
       }  
     }  
     prev->next = NULL;  
     return head;  
   }  

LeetCode: Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  

   typedef ListNode node; 

 
   ListNode *deleteDuplicates(ListNode *head) {  
     if(!head || !head->next)return head;  
     ListNode *prev = NULL,*cur = head, *newHead = NULL;  
     while(cur)  
     {  
       node *nxt = cur->next;  
       bool deleteCur = false;  
       while(nxt && nxt->val == cur->val)  
       {  
         deleteCur = true;  
         node *tmp = nxt;  
         cur->next = nxt->next;  
         nxt = nxt->next;  
         delete tmp;  
       }  
       if(deleteCur)  
       {  
         node *tmp = cur;  
         if(prev)  
           prev->next = nxt;  
         cur = nxt;  
         if(nxt)  
           nxt = nxt->next;  
         delete tmp;  
       }  
       else  
       {  
         if(!prev)newHead = cur;  
         prev = cur;  
         cur = nxt;  
         if(nxt)  
           nxt = nxt->next;   
       }  
     }  
     return newHead;  
   }  

LeetCode: Reverse Linked List II

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.

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
   typedef ListNode ln; 

 
   ln *reverse(ln *prev, ln *cur, ln *nxt, int n, ln **lastNode)  
   {  
     int cnt = 0;  
     ln *head = cur;  
     while(cur && cnt != n+1)  
     {  
       cnt++;  
       cur->next = prev;  
       prev = cur;  
       cur = nxt;  
       if (nxt)  
         nxt = nxt->next;  
     }  
     if(cur)  
       head->next = cur;  
     if(!cur)*lastNode = prev;  
     return prev;  
   }  

   ListNode *reverseBetween(ListNode *head, int m, int n) {  
     if(!head || !head->next || (n-m<1))return head;  
     ln *prev = NULL, *cur=head, *nxt = head->next, *newHead = NULL;  
     int cnt = 1;  
     newHead = head;  
     while(cur && cnt!=m)  
     {  
       cnt++;  
       prev = cur;  
       cur = nxt;  
       if(nxt)  
         nxt = nxt->next;  
     }  
     ln *lastNode = NULL,*revHead = NULL;  
     revHead = reverse(NULL,cur,nxt, n-m, &lastNode);  
     if(prev)  
       prev->next = revHead;  
     else if(lastNode)  
       newHead = lastNode;  
     else newHead = revHead;  
     return newHead;  
   }  

LeetCode: Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  

 /**  
  * Definition for binary tree  
  * struct TreeNode {  
  *   int val;  
  *   TreeNode *left;  
  *   TreeNode *right;  
  *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
  * };  
  */  

   TreeNode *sortedListToBST(ListNode *head) {  
     if(!head)return NULL;  
     TreeNode *root = new TreeNode(head->val);  
     if(!head->next)return root;  
     ListNode *fast = head->next, *slow = head, *prev;  
     while(fast)  
     {  
       prev = slow;  
       slow = slow->next;  
       if(fast->next)  
         fast = fast->next->next;  
       else fast = fast->next;  
     }  
     root->val = slow->val;  
     prev->next = NULL;  
     root->left = sortedListToBST(head);  
     root->right = sortedListToBST(slow->next);  
     return root;  
   }  

LeetCode: Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 
     typedef ListNode ln;


     ListNode *detectCycle(ListNode *head) {  
     if(!head || !head->next)return NULL;  
     ln *fast = head, *slow = head;  
     while(fast && fast->next)  
     {  
       slow = slow->next;  
       fast = fast->next->next;  
       if(fast == slow)break;  
     }  
     if(fast != slow)return NULL;  
     ln *first = head, *second = slow;  
     while(first != second)  
     {  
       first = first->next;  
       second = second->next;  
     }  
     return first;  
   }  

LeetCode: Linked List Cycle

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
     typedef ListNode ln;


     bool hasCycle(ListNode *head) {  
     if(!head || !head->next)return false;  
     ln *slow=head, *fast=head;  
     while(fast && fast->next)  
     {  
       slow = slow->next;  
       fast = fast->next->next;  
       if(slow == fast)return true;  
     }  
     return false;  
   }  

LeetCode: Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
   typedef ListNode ln;


   ln *reverse(ln *head)  
   {  
     if(!head || !head->next)return head;  
     ln *prv = NULL, *cur=head, *nxt=head->next;  
     while(cur)  
     {  
       cur->next = prv;  
       prv = cur;  
       cur = nxt;  
       if(nxt)  
         nxt = nxt->next;  
     }  
     return prv;  
   }


  
   void reorderList(ListNode *head) {  
     if(!head || !head->next || !head->next->next)return;  
     ln *fast=head, *slow=head, *prev;  
     while(fast && fast->next)  
     {  
       prev = slow;  
       slow = slow->next;  
       fast = fast->next->next;  
     }  
     if(fast){prev = slow; slow = slow->next;}  
     prev->next = NULL;  
     ln *second = reverse(slow), *first = head;  
     while(first && second)  
     {  
       ln *tmp1 = first->next;  
       ln *tmp2 = second->next;  
       first->next = second;  
       second->next = tmp1;  
       second = tmp2;  
       first = tmp1;  
     }  
   }  

LeetCode: Sort List

Sort a linked list in O(n log n) time using constant space complexity.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 typedef ListNode ln;


   ListNode *Merge(ln *a, ln *b)  
   {  
     if(!a && !b)return a;  
     if(!a)return b;  
     if(!b)return a;  
     ln *t1 = a, *t2 = b,*prev = NULL;  
     ln *head = a->val<=b->val?a:b;  
     while(t1 && t2)  
     {  
       if(t1->val <= t2->val)  
       {  
         prev = t1;  
         t1 = t1->next;  
       }  
       else  
       {  
         if(prev)  
         {  
           prev->next= t2;  
         }  
         ln *tmp = t2->next;  
         t2->next = t1;  
         prev = t2;  
         t2 = tmp;  
       }  
     }  
     if(!t1)prev->next = t2;  
     return head;  
   }
   

  
   ListNode *MergeSort(ListNode *head) {  
     if(!head || !head->next)return head;  
     ln *fast=head, *slow=head, *prev;  
     while(fast && fast->next)  
     {  
       fast = fast->next->next;  
       prev = slow;  
       slow = slow->next;  
     }  
     prev->next = NULL;  
     ln *first = head, *second = slow;  
     ln *x = MergeSort(first);  
     ln *y = MergeSort(second);  
     head = Merge(x,y);  
     return head;  
   }  
   ListNode *sortList(ListNode *head) {  
     return MergeSort(head);  
   }