## (Merge k Sorted Lists)

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

Thoughts:
We start with the first list and then merge it with the second list, then the third list, so on and the so forth. For merging two sorted linked list, we use the linear merging algorithm borrowed from Merge Sort. The total complexity is $O(kn)$.

Code (Java):

public class Solution {
public ListNode mergeKLists(ArrayList<ListNode> lists) {
for (ListNode node : lists)
}

} else {
}
}
}

Code (C++):
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
for(int i = 0; i < lists.size(); ++i)
}

private:

} else {
}
}
};



## (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.

Thoughts:
This question is the same as ‘remove duplicates from sorted array’ except that we need to deal with linked list this time. The algorithm is the same.

Code (Java):

public class Solution {
return null;
while(i != null) {
if(j.val != i.val) {
j = j.next;
j.val = i.val;
}
i = i.next;
}
j.next = null;
}
}


Code (C++):

class Solution {
public:
ListNode *i = j -> next;
while(i != NULL) {
if(i -> val != j -> val) {
j = j -> next;
j -> val = i -> val;
}
i = i -> next;
}
j -> next = NULL;
}
};


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.
IUNPUT: (2 -> 4 -> 3) + (5 -> 6 -> 4) (i.e. 342 + 465)
OUTPUT: 7 -> 0 -> 8 (i.e. 342 + 465 = 807)

Thoughts:
We just add element by element, as the way we manually do addition. We need to take care of two things:

1. We should not forge the carry, especially when we have one more digit just for the carry. (e.g., 5 + 7 = 12, the ‘1’ in 12 is due to the carry from last digit)
2. We should be careful about the fact that these two numbers might not be of the same digits. (e.g., 7 + 3456)

Code (Java):

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int carry = 0;
ListNode l3 = null;
ListNode iter = null;
while(l1 != null || l2 != null) {
int v1 = l1 == null ? 0 : l1.val;
int v2 = l2 == null ? 0 : l2.val;
int sum = (v1 + v2 + carry) % 10;
carry = (v1 + v2 + carry) / 10;

ListNode node = new ListNode(sum);
node.next = null;
if(l3 == null) {
iter = node;
l3 = node;
} else {
iter.next = node;
iter = node;
}

l1 = l1 == null? null : l1.next;
l2 = l2 == null? null : l2.next;
}
if(carry != 0) {
ListNode node = new ListNode(carry);
node.next = null;
iter.next = node;
iter = node;
}
return l3;
}
}

Code (C++):
/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
int carry = 0;
ListNode *l3 = NULL;
ListNode *iter = NULL;
while(l1 != NULL || l2 != NULL) {
int v1 = l1 == NULL ? 0 : l1->val;
int v2 = l2 == NULL ? 0 : l2->val;
int sum = (v1 + v2 + carry) % 10;
carry = (v1 + v2 + carry) / 10;

ListNode *node = new ListNode(sum);
if(l3 == NULL) {
iter = node;
l3 = node;
} else {
iter->next = node;
iter = node;
}

l1 = l1 == NULL? NULL : l1->next;
l2 = l2 == NULL? NULL : l2->next;
}
if(carry != 0) {
ListNode *node = new ListNode(carry);
node->next = NULL;
iter->next = node;
iter = node;
}
return l3;
}
};



## Create linked lists of all the nodes at each depth for a BST

Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (i.e., if you have a tree with depth D, you’ll have D linked lists)

My initial thoughts:
We just do a level-order traversal throughout the tree. For each level, create a linked list containing all the nodes at that depth. Then extract all of the children for each node to create the next linked list at deeper level.

My initial codes:


BinaryTreeNode root) {
int index = 0;

while (true) {
for (int i = 0; i < upperLevel.size(); ++i) {
BinaryTreeNode parent = upperLevel.get(i);
}
if (!leveli.isEmpty()) {
index++;
} else {
break;
}
}

return lists;
}

NullPointerException in highlighted line 14 and 15. Need to check whether left or right exists before putting into the linked-list. Correction:
if (parent.getLeft() != null)
if (parent.getRight() != null)

Solution:
The solution is identical to my codes:
BinaryTreeNode root) {
int level = 0;
while (true) {
for (int i = 0; i < result.get(level).size(); i++) {
BinaryTreeNode n = result.get(level).get(i);
if (n != null) {
if (n.getLeft() != null)
if (n.getRight() != null)
}
}
if (list.size() > 0) {
} else {
break;
}
level++;
}
return result;
}



## Find loop starting point in a circular linked list

Given a circular linked list, implement an algorithm which returns node at the beginning of the loop.
DEFINITION
A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.
EXAMPLE
input: A -> B -> C -> D -> E -> C [the same C as earlier]
output: C

My initial thoughts:
Initialize with two pointers to the head, the slow pointer and fast pointer. Each time, slow pointer moves one step while the fast pointer moves two steps. If they meet in the some point, then that node must be the starting point of the loop.

My initial codes:

	public static LLNode findLoopBeginningPoint(

fastPointer = fastPointer.getNext();
fastPointer = fastPointer.getNext();

while (slowPointer != fastPointer) {
slowPointer = slowPointer.getNext();
fastPointer = fastPointer.getNext();
fastPointer = fastPointer.getNext();
}

return slowPointer;
}

The testing input yields out ‘E’ instead of the expected result ‘C’. Walk through the code:

fastPointer: ‘C’; slowPointer: ‘A’
fastPointer: ‘E’; slowPointer: ‘B’
fastPointer: ‘D’; slowPointer: ‘C’
fastPointer: ‘C’; slowPointer: ‘D’
fastPointer: ‘E’; slowPointer: ‘E’

The catch point of this algorithm is that when the fast pointer meets the slow pointer, the distance between their meeting point and the starting point of the loop, is equal to the distance between the head of the list and the starting point of the loop.
Let us denote the length of non-loop list as $m$, i.e., the distance between the head of the list to the starting point of the loop is $m$. Let’s also have the size of the loop as $L$. When the two pointer meets, let us denote the distance between the meeting point of the starting of the loop as $d$. So, at the time of their meet, the fast pointer would have travelled $m+nL-d$ and the slow pointer only travelled $m+L-d$. Therefore we have $m+nL-d=2(m+L-d) \Leftrightarrow d\equiv m \pmod L$.
Therefore, when the two pointer meets, we can move one pointer to the head, and then move them one step at each time, when they meet again, they will meet at the starting pointer of the loop.
public static LLNode<Character> findLoopBeginningPoint(

do {
slowPointer = slowPointer.getNext();
fastPointer = fastPointer.getNext().getNext();
} while (slowPointer != fastPointer);

if (slowPointer == null)
return null;

while (slowPointer != fastPointer) {
slowPointer = slowPointer.getNext();
fastPointer = fastPointer.getNext();
}

return slowPointer;
}

If the linked list has no loop, the highlighted line will raise an null-pointer exception under some circumstances.
Solution
public static LLNode<Character> FindBeginning(LLNode<Character> head) {

// find meeting point
while (n2.getNext() != null) {
n1 = n1.getNext();
n2 = n2.getNext().getNext();
if (n1 == n2)
break;
}

// Error check - there is no meeting point, and therefore no loop
if (n2.getNext() == null)
return null;

/*
* Move n1 to Head. Keep n2 at Meeting Point. Each are k steps from the
* Loop Start. If they move at the same pace, they must meet at Loop
* Start.
*/
while (n1 != n2) {
n1 = n1.getNext();
n2 = n2.getNext();
}

return n2;
}



You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
EXAMPLE
Input: (3 -> 1 -> 5) + (5 -> 9 -> 2)
Output: 8 -> 0 -> 8

My initial thoughts:
Add up numbers nodes by nodes. Take care of carries. In each summation of two digits:
sum digit = (digit1 + digit2 + carry_from_previous) % 10;
carry = (digit1 + digit2 + carry_from_previous) – 10;
There are generally three cases needed to be handled:

• digit1 and digit2 are neigher null
• digit1 is null
• digit2 is null

My initial codes:

	public static LLNode<Integer> addWithCarry(LLNode<Integer> head1,
LLNode<Integer> node = carry ? new LLNode<Integer>(1) : null;
return node;
}
int sum = carry ? (number1 + number2 + 1) % 10
: (number1 + number2) % 10;
boolean carryNext = carry ? number1 + number2 + 1 >= 10
: (number1 + number2) >= 10;
LLNode<Integer> node = new LLNode<Integer>(sum);
carryNext));
else
return node;
}

Solution
LLNode<Integer> l2, int carry) {
if (l1 == null && l2 == null)
return null;
LLNode<Integer> result = new LLNode<Integer>(carry);
int value = carry;
if (l1 != null)
value += l1.getData();
if (l2 != null)
value += l2.getData();
result.setData(value % 10);
LLNode<Integer> more = addList(l1 == null ? null : l1.getNext(),
l2 == null ? null : l2.getNext(), value > 10 ? 1 : 1);
result.setNext(more);
return result;
}

There are two mistakes in this solution. Highlighted line 4. If l1 and l2 are both null, you still need to consider the carry: 1 + 9->1 = 0->0->1 but this solution will output 0->0. Highlighted line 13: should be:
value >= 10 ? 1 : 0



Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node. EXAMPLE
Input: the node ‘c’ from the linked list a->b->c->d->e
Result: nothing is returned, but the new linked list looks like a->b->d->e

My initial thoughts:
We need to consider two cases: if that node is the head, then we need to update head pointer to the next one. If that node is in the middle, then we need to update the previous pointer.

My initial codes:


public static void deleteANode(LLNode head, LLNode item) {
item.setNext(null);
return;
}
while (current != null) {
if (current == item) {
previous.setNext(current.getNext());
current.setNext(null);
return;
} else {
previous = current;
current = current.getNext();
}
}
return;
}

It works fine with O(n) time complexity and O(1) space complexity.
After reading the solution, I found out that the question explicitly specifies that only the access to that node is given therefore you don’t know the head pointer.

Solution:
public static void deleteNode(LLNode node) {
if (node == null || node.getNext() == null)
return;
LLNode nextNode = node.getNext();
node.setData(nextNode.getData());
node.setNext(nextNode.getNext());
nextNode.setNext(null);
}

If that node happens to be at the end, then there’s no way to delete it without knowing the previous node.



## Find nth to last element of a singly linked list

Implement an algorithm to find the nth to last element of a singly linked list.

My initial thoughts:
Finding the nth to last element = Finding the (size – n + 1) first element. So we first get the size of the list and then traverse from the beginning.

My initial codes:

	public static LLNode<Integer> nthLastElement(LLNode<Integer> head, int n) {
int size = 0;
while (current != null) {
size++;
current = current.getNext();
}
int pos = size - n + 1;
int i = 1;
if (pos == 1)
else
do {
i++;
current = current.getNext();
} while (current != null && i != pos);
return current;
}

Works fine for most inputs. Time complexity O(n) and space complexity O(1).
Failed for empty list. Add one sentence after highlighted line:
if(head == null || n < 0 || n > size) return null;

Solution:
The solution gives another insight of this question:

Create two pointers, p1 and p2, that point to the beginning of the node.
Increment p2 by n-1 positions, to make it point to the nth node from the beginning (to make the distance of n between p1 and p2).
Check for p2->next == null if yes return value of p1, otherwise increment p1 and p2. If next of p2 is null it means p1 points to the nth node from the last as the distance between the two is n.
Repeat Step 3.

public static LLNode<Integer> nthToLast(LLNode<Integer> head, int n) {
if (head == null || n < 1) {
return null;
}
for (int j = 0; j < n - 1; ++j) { // skip n-1 steps ahead
if (p2 == null) {
}
p2 = p2.getNext();
}
while (p2.getNext() != null) {
p1 = p1.getNext();
p2 = p2.getNext();
}
return p1;
}



## Remove duplicates from an unsorted Linked List

Write code to remove duplicates from an unsorted linked list.
How would you solve this problem if a temporary buffer is not allowed?

My initial thoughts:
Because we don’t want to use any large space, we can keep record of two iterators to go through the entire list and check to see if there are duplicates. So that’s an O(n^2) time complexity and O(1) space complexity solution.

My initial codes (solution):

	public static void removeDuplicates(LLNode<Integer> head) {

while (left.getNext() != null) {
LLNode<Integer> previous = left;
LLNode<Integer> right = left.getNext();
do {
if (right.getData() == left.getData()) {
previous.setNext(right.getNext());
right.setNext(null);
right = previous.getNext();
} else {
previous = right;
right = right.getNext();
}
} while (right != null);
left = left.getNext();
}

}

It works fine for multiple elements, multiple duplicates, etc.
Failed for 1 -> 1.

Correction:

public static void removeDuplicates(LLNode<Integer> head) {

while (left != null) {
LLNode<Integer> previous = left;
LLNode<Integer> right = left.getNext();
while (right != null) {
if (right.getData() == left.getData()) {
previous.setNext(right.getNext());
right.setNext(null);
right = previous.getNext();
} else {
previous = right;
right = right.getNext();
}
}
left = left.getNext();
}

}

Solution:
public static void deleteDups2(LLNode<Integer> head) {
return;
LLNode<Integer> current = previous.getNext();
while (current != null) {
while (runner != current) { // Check for earlier dups
if (runner.getData() == current.getData()) {
LLNode<Integer> tmp = current.getNext(); // remove current
previous.setNext(tmp);
current = tmp; // update current to next node
break; // all other dups have already been removed
}
runner = runner.getNext();
}
if (runner == current) { // current not updated - update now
previous = current;
current = current.getNext();
}
}
}