(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) {
		ListNode head = null;
		for (ListNode node : lists)
			head = mergeTwoLists(head, node);
		return head;
	}

	private ListNode mergeTwoLists(ListNode head1, ListNode head2) {
		if (head1 == null || head2 == null)
			return head1 == null ? head2 : head1;

		if (head1.val < head2.val) {
			head1.next = mergeTwoLists(head1.next, head2);
			return head1;
		} else {
			head2.next = mergeTwoLists(head2.next, head1);
			return head2;
		}
	}
}

Code (C++):

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        ListNode *head = NULL;
    	for(int i = 0; i < lists.size(); ++i)
			head = mergeTwoLists(head, lists[i]);
		return head;
    }

private: 
    ListNode *mergeTwoLists(ListNode *head1, ListNode *head2) {
		if (head1 == NULL || head2 == NULL)
			return head1 == NULL ? head2 : head1;

        if (head1 -> val < head2 -> val) {
			head1 -> next = mergeTwoLists(head1 -> next, head2);
            return head1;
		} else {
			head2 -> next = mergeTwoLists(head2 -> next, head1);
            return head2;
		}
	}
};

(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 {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null)
            return null;
        ListNode j = head;
        ListNode i = head.next;
        while(i != null) {
            if(j.val != i.val) {
                j = j.next;
                j.val = i.val;
            }
            i = i.next;
        }
        j.next = null;
        return head;
    }
}

Code (C++):

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        if(head == NULL)
            return head;
        ListNode *j = head;
        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;
        return head;
    }
};

Adding two linked-list representations of numbers (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.
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):

/**
 * Definition for singly-linked list.
 * 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++):

/**
 * Definition for singly-linked list.
 * 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:


	public static List<LinkedList<BinaryTreeNode>> createLinkedLists(
			BinaryTreeNode root) {
		List<LinkedList<BinaryTreeNode>> lists = new ArrayList<LinkedList<BinaryTreeNode>>();
		LinkedList<BinaryTreeNode> level0 = new LinkedList<BinaryTreeNode>();
		level0.add(root);
		lists.add(level0);
		int index = 0;

		while (true) {
			LinkedList<BinaryTreeNode> leveli = new LinkedList<BinaryTreeNode>();
			LinkedList<BinaryTreeNode> upperLevel = lists.get(index);
			for (int i = 0; i < upperLevel.size(); ++i) {
				BinaryTreeNode parent = upperLevel.get(i);
					leveli.add(parent.getLeft());
					leveli.add(parent.getRight());
			}
			if (!leveli.isEmpty()) {
				lists.add(leveli);
				index++;
			} else {
				break;
			}
		}

		return lists;
	}

Comments after running:
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)
					leveli.add(parent.getLeft());
				if (parent.getRight() != null)
					leveli.add(parent.getRight());

Solution:
The solution is identical to my codes:

	public static ArrayList<LinkedList<BinaryTreeNode>> findLevelLinkList(
			BinaryTreeNode root) {
		int level = 0;
		ArrayList<LinkedList<BinaryTreeNode>> result = new ArrayList<LinkedList<BinaryTreeNode>>();
		LinkedList<BinaryTreeNode> list = new LinkedList<BinaryTreeNode>();
		list.add(root);
		result.add(level, list);
		while (true) {
			list = new LinkedList<BinaryTreeNode>();
			for (int i = 0; i < result.get(level).size(); i++) {
				BinaryTreeNode n = result.get(level).get(i);
				if (n != null) {
					if (n.getLeft() != null)
						list.add(n.getLeft());
					if (n.getRight() != null)
						list.add(n.getRight());
				}
			}
			if (list.size() > 0) {
				result.add(level + 1, list);
			} 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
Circular linked list:
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(
			LLNode head) {
		LLNode slowPointer = head;
		LLNode fastPointer = head;

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

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

		return slowPointer;
	}

Comments after running:
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(
			LLNode<Character> head) {
		LLNode<Character> slowPointer = head;
		LLNode<Character> fastPointer = head;

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

		if (slowPointer == null)
			return null;

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

		return slowPointer;
	}

Comments after running
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) {
		LLNode<Character> n1 = head;
		LLNode<Character> n2 = 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.
		 */
		n1 = head;
		while (n1 != n2) {
			n1 = n1.getNext();
			n2 = n2.getNext();
		}

		return n2;
	}

Add up two linked list representations of numbers

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> head2, boolean carry) {
		if (head1 == null && head2 == null) {
			LLNode<Integer> node = carry ? new LLNode<Integer>(1) : null;
			return node;
		}
		int number1 = head1 == null ? 0 : head1.getData();
		int number2 = head2 == null ? 0 : head2.getData();
		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);
		if (head1 != null && head2 != null)
			node.setNext(addWithCarry(head1.getNext(), head2.getNext(),
					carryNext));
		else if (head1 == null)
			node.setNext(addWithCarry(null, head2.getNext(), carryNext));
		else
			node.setNext(addWithCarry(head1.getNext(), null, carryNext));
		return node;
	}

Solution

	public static LLNode<Integer> addList(LLNode<Integer> l1,
			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;
	}

Comments:
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

Delete a node in a singly linked list given only access to that node

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) {
		if (head == item) {
			head = item.getNext();
			item.setNext(null);
			return;
		}
		LLNode previous = head, current = head;
		while (current != null) {
			if (current == item) {
				previous.setNext(current.getNext());
				current.setNext(null);
				return;
			} else {
				previous = current;
				current = current.getNext();
			}
		}
		return;
	}

Comments after running:

  • 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);
	}

Comments:

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

Previous Older Entries