Coding Problems and Solutions-8
[1] Remove Nth Node From End of List — Given a linked list, remove the n-th node from the end of list and return its head.
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.
(https://leetcode.com/problems/remove-nth-node-from-end-of-list/)
Approach — Use 2 pointer approach. One pointer is n+1 nodes ahead of the other. When the forward pointer reaches the end, the backward pointer’s next node is to be removed.
[2] Reverse Nodes in k-Group — Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
Example:
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
(https://leetcode.com/problems/reverse-nodes-in-k-group/)
Approach — Use recursion.
To reverse k nodes, use swapping technique. Delete the node at i-th position (i < k) and put it at the head of the list. Repeat for all i < k.
Do this recursively for the remaining list from position k onwards.
[3] Rotate List — Given a linked list, rotate the list to the right by k places, where k is non-negative.
Example:
Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL(https://leetcode.com/problems/rotate-list/)
Approach — Find the length ‘h’ of the list. If k > h then use k = k % h. Then using 2 pointer approach, remove the last k nodes of the list and add it to front of the list.
The 2 pointers should be distance k+1 apart, so that when the forward pointer reaches the end of the list the backward pointer’s next pointer should be removed.
[4] Remove Duplicates from Sorted List — Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
Return the linked list sorted as well.
Example:
Input: 1->2->3->3->4->4->5
Output: 1->2->5(https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
Approach — Use recursion.
If the value of current node is same as the previous node value or the value of next node is same as current node value then do not return the current node else return the current node. Recursively add the next node to the current node.
To maintain previous node value use an additional parameter in the function for the previous node value.
[5] 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.
Example:
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5(https://leetcode.com/problems/partition-list/)
Approach — Use quick-select approach.
Use 2 pointers, p and q. Pointer p is the current node and q points to the node whose next node is greater than ≥ x. If the value of p’s next node is < x, then swap p’s next node with q’s next node and move q ahead by 1 node. This will guarantee that all nodes with values < x are before all nodes with values ≥ x.
[6] Reverse Linked List — Reverse a linked list from position m to n. Do it in one-pass.
Note: 1 ≤ m ≤ n ≤ length of list.
Example:
Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL(https://leetcode.com/problems/reverse-linked-list-ii/)
Approach — Use 2 pointer approach.
First advance both pointers to (m-1)-th position, then advance only one pointer to (n-1)-th position. Use swapping to reverse the linked list from m to n-th position.
[7] 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.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example:
Given the sorted linked list: [-10,-3,0,5,9],One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST: 0
/ \
-3 9
/ /
-10 5
(https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/)
Using O(N) extra space:
Approach — Use a map to store the node corresponding to the index in the list.
Then select the middle node as the root of the BST and recursively build the left and right subtrees corresponding to the indices before and after the middle index.
Without extra space:
Approach — Use 3 pointers, (p, q and p_prev)
p_prev is the previous node of p.
Advance p by 1 node and q by 2 nodes each time. Thus when q reaches the tail, p will be at the middle node.
Make p the root of the BST and recursively build the left subtree with the list from head to p_prev and right subtree with the list from p.next to tail.
[8] Linked List Cycle — Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Note: Do not modify the linked list.
Example:
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.(https://leetcode.com/problems/linked-list-cycle-ii/)
Approach — If there is a cycle, then using 2 pointer approach where one pointer is advanced by 2 steps and another by one step, these are bound to meet at some node (after the starting point).
The 2 pointers will meet again after number of steps equals to the length of the cycle.
Again using 2 pointers where one is ahead of the other by length of cycle number of steps, the 2 pointers will meet at the starting node of the cycle.
[9] 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 may not modify the values in the list’s nodes, only nodes itself may be changed.
Example:
Given 1->2->3->4, reorder it to 1->4->2->3.(https://leetcode.com/problems/reorder-list/)
Approach — Use map to store the node corresponding to the index.
Then recursively reorder the list. For start and end indices i and j, add the node corresponding to j as the next node of i. Recursively doing this for i+1-th node to j-1-th node. Add the head of the list from i+1-th node to j-1-th node as the next node of the j-th node.
[10] Sort List — Sort a linked list in O(n log n) time using constant space complexity.
Example:
Input: 4->2->1->3
Output: 1->2->3->4(https://leetcode.com/problems/sort-list/)
Approach — Use merge sort.
[11] Add Two Numbers — You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.
Example:
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7(https://leetcode.com/problems/add-two-numbers-ii/)
Approach — Use recursion.
Compute the length of the 2 lists first call them n1 and n2.
If n1 > n2 then recursively return the head node and carry of the list l1.next and l2 and compute the new sum as (c + l1.val)%10 and new carry as (c+l1.val)/10.
If n1 < n2 then recursively return the head node and carry of the list l1 and l2.next and compute the new sum as (c + l2.val)%10 and new carry as (c+l2.val)/10.
If n1 == n2, then recursively return the head node and carry of the list l1.next and l2.next and compute the new sum as (c + l1.val + l2.val)%10 and new carry as (c + l1.val + l2.val)/10.
