# SE103 Week 1 Post Session Solutions
[Add Two Numbers](#Add-two-numbers-MSF)
[Copy List With Random Pointer](#Copy-List-With-Random-Pointer)
[Intersection of Two Lists](#Intersection-of-Two-Lists)
[Merge K Sorted Lists](#Merge-K-Sorted-Lists)
[Merge Two Sorted Lists](#Merge-Two-Sorted-Lists)
[Remove Duplicates II](#Remove-Duplicates-II)
[Reorder List](#Reorder-List)

## Add two numbers (MSF)
**Java**

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode previous = null;
        while (head != null) {
            ListNode next_head = head.next;
            head.next = previous;
            previous = head;
            head = next_head;
        }
        return previous;
    }
    public ListNode addTwoNumbersLSF(ListNode l1, ListNode l2) {
        ListNode resultList = new ListNode(0);
        // Create a variable for walking the resulting list
        ListNode cur = resultList;

        // Track the previous node so that we can remove the current node if it
        // turned out to be unnecessary.
        ListNode prev = null;
        while (l1 != null || l2 != null) {
            if (l1 != null) {
                cur.val += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                cur.val += l2.val;
                l2 = l2.next;
            }
            // Create the next node with a value of 1 iff there is a digit
            // carried from this iteration; otherwise it has a value of 0.
            cur.next = new ListNode(cur.val / 10);
            cur.val %= 10;
            prev = cur;
            cur = cur.next;
        }

        // If the most recently added node has value 0, then it is a leading
        // zero and can be truncated.
        if (cur.val == 0) {
            prev.next = null;
        }
        return resultList;
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        l1 = reverseList(l1);
        l2 = reverseList(l2);
        ListNode result = addTwoNumbersLSF(l1, l2);
        return reverseList(result);
    }
}

**Python**

# Reverse both linked lists, then use the same algorithm as the variation of
# this problem with the least significant digit first. Finally, reverse the
# result to get the solution in most signficiant digit first form and return
# it. Since reversing a linked list is linear time and the original algorithm
# was linear time, the running time of this algorithm is also linear time.
class Solution(object):
    def reverseList(self, head):
        previous = None
        while head:
            next_head = head.next
            head.next = previous
            previous = head
            head = next_head
        return previous

    def addTwoNumbersLSF(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        resultList = ListNode(0)
        # Create a variable for walking the resulting list
        cur = resultList

        # Track the previous node so that we can remove the current node if it
        # turned out to be unnecessary.
        prev = None
        while l1 or l2:
            if l1:
                cur.val += l1.val
                l1 = l1.next
            if l2:
                cur.val += l2.val
                l2 = l2.next
            # Create the next node with a value of 1 iff there is a digit
            # carried from this iteration; otherwise it has a value of 0.
            cur.next = ListNode(cur.val / 10)
            cur.val %= 10
            prev = cur
            cur = cur.next

        # If the most recently added node has value 0, then it is a leading
        # zero and can be truncated.
        if cur.val == 0:
            prev.next = None
        return resultList

    def addTwoNumbers(self, l1, l2):
        l1 = self.reverseList(l1)
        l2 = self.reverseList(l2)
        result = self.addTwoNumbersLSF(l1, l2)
        return self.reverseList(result)

## Copy List With Random Pointer
**Python**

# The primary challenge in this problem is finding the node in the copied list
# corresponding to a particular node in the original list (to assign the proper
# value for the random pointer).
#
# One solution, which uses O(n) storage, is to create a hashtable which maps
# each node in the original list to a node in the copy of the list. Then, one
# could copy the list in a single pass, and correct the random pointers in a
# second pass by looking up the corresponding node in the hashtable.
#
# Another solution, which takes O(n^2) time, is to do a linear search through
# the original list to find the position of the random node and iterate to the
# corresponding position in the copied list.
#
# The solution below arranges the copied nodes to initially live immediately
# after their corresponding original node. This makes it easy to find all the
# random pointers in constant time without extra storage. After the random
# pointers have been assigned, the list is peeled apart like a zipper; all the
# odd nodes return to the original list and all the even nodes form the copied
# list.
class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        if not head:
            return None
        # Step 1: Duplicate each node and put it after the existing node.
        cur = head
        while cur:
            originalNext = cur.next
            cur.next = RandomListNode(cur.label)
            cur.next.next = originalNext
            cur = originalNext

        # Step 2: Copy all the random pointers
        cur = head
        while cur:
            copyCur = cur.next
            if cur.random:
                copyCur.random = cur.random.next
            cur = cur.next.next

        # Step 3: Peel the list apart, and return the new copy
        cur = head
        copyHead = head.next
        copyCur = copyHead

        # Remainder of the combined list
        combined = head.next.next
        isCopy = False

        while combined:
            if not isCopy:
                cur.next = combined
                cur = cur.next
            else:
                copyCur.next = combined
                copyCur = copyCur.next
            isCopy = not isCopy
            combined = combined.next

        cur.next = None
        return copyHead

**Java**

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null)
            return null;
        // Step 1: Duplicate each node and put it after the existing node.
        RandomListNode cur = head;
        while (cur != null) {
            RandomListNode originalNext = cur.next;
            cur.next = new RandomListNode(cur.label);
            cur.next.next = originalNext;
            cur = originalNext;
        }

        // Step 2: Copy all the random pointers
        cur = head;
        while (cur != null) {
            RandomListNode copyCur = cur.next;
            if (cur.random != null)
                copyCur.random = cur.random.next;
            cur = cur.next.next;
        }

        // Step 3: Peel the list apart, and return the new copy
        cur = head;
        RandomListNode copyHead = head.next;
        RandomListNode copyCur = copyHead;

        // Remainder of the combined list
        RandomListNode combined = head.next.next;
        boolean isCopy = false;

        while (combined != null) {
            if (!isCopy) {
                cur.next = combined;
                cur = cur.next;
            }
            else {
                copyCur.next = combined;
                copyCur = copyCur.next;
            }
            isCopy = !isCopy;
            combined = combined.next;
        }

        cur.next = null;
        return copyHead;
    }
}

## Intersection of Two Lists
**Python**

# If two lists intersect and have different lengths, then the difference must
# show up in the non-intersecting parts of the list. Therefore, iterate through
# the longer list until the two lists are the same length, and then iterate the
# lists together to find the intersecting node if it exists.
# Computing the length of a linked list is a linear time operation. Iterating
# over the two lists together is also a linear time operation. Therefore, the
# overall running time is O(n).

class Solution(object):
    def getLen(self, headA):
        s = 0
        while headA:
            headA = headA.next
            s+=1
        return s

    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        Alen = self.getLen(headA)
        Blen = self.getLen(headB)
        if Alen < Blen:
            delta = Blen - Alen
            # Advance B's head until the two lists are the same length.
            for _ in xrange(delta):
                headB = headB.next
        else:
            delta = Alen - Blen
            # Advance A's head until the two lists are the same length.
            for _ in xrange(delta):
                headA = headA.next
        while headA:
            if headA == headB:
                return headA
            headA = headA.next
            headB = headB.next
        return None

**Java**

public class Solution {
    public int getLen(ListNode head) {
        int count = 0;
        while (head != null) {
            head = head.next;
            count++;
        }
        return count;
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int Alen = getLen(headA);
        int Blen = getLen(headB);
        if (Alen < Blen) {
            int delta = Blen - Alen;
            // Advance B's head until the two lists are the same length.
            for (int i = 0; i < delta; i++)
                headB = headB.next;
        }
        else {
            int delta = Alen - Blen;
            // Advance A's head until the two lists are the same length.
            for (int i = 0; i < delta; i++)
                headA = headA.next;
        }
        while (headA != null) {
            if (headA == headB)
                return headA;
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }
}

## Merge K Sorted Lists
**Python**

# In the standard algorithm for merging two sorted linked lists, each step of
# the algorithm compares the head nodes of each list, and removes the smaller
# head, adding it to the merged list.
# A naive solution to this problem uses a linear search to find the
# minimum of the k heads at every iteration, but the running time would be 
# O(kn), where k is the number of linked lists and n is the sum of the length
# of each linked list.
# The solution below holds the smallest node in each linked list in a heap, a
# data structure in which both extraction of the smallest element and insertion
# of any element is O(log k).  The heap is initialized with the smallest
# element from each list. At each iteration, the smallest element from the
# heap is added to the output linked list, and its child node (if not null) is
# added into the heap. The algorithm iterates until all the origial lists are
# exhausted. Since each iteration takes 2 operations which take O(log k) time
# and there are n iterations, the overall running time is O(n log k).
import heapq

# Python's heapq interface is a little verbose and doesn't support keys; this
# class is a thin wrapper that makes it slightly easier to deal with.
class Heap:
    def __init__(self, key=lambda x: x):
        self.storage = []
        self.key = key

    # Discard attempts to push None.
    def push(self, item):
        if item:
            heapq.heappush(self.storage, (self.key(item), item))

    def pop(self):
        try:
            _, item = heapq.heappop(self.storage)
            return item
        except:
            return None

    def length(self):
        return len(self.storage)


class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        # Initialize: Add the smallest node from each list into the heap.
        minElements = Heap(key=lambda x : x.val)

        for i in xrange(len(lists)):
            if lists[i]:
                minElements.push(lists[i])
                lists[i] = lists[i].next

        # Use the dummy head node to avoid handling the first element
        # differently than the remaining elements.
        dummyHead = ListNode("dummy")
        parent = dummyHead

        # Take the smallest element in the heap, and push its child
        # onto the heap.
        while minElements.length() != 0:
            cur = minElements.pop()
            minElements.push(cur.next)
            parent.next = cur
            parent = parent.next
        return dummyHead.next

**Java**

class Solution {
    static class ListNodeComparator implements Comparator<ListNode> {
        public int compare(ListNode a, ListNode b) {
            return a.val - b.val;
        }
    }
    public ListNode mergeKLists(ListNode[] lists) {
        // Initialize: Add the smallest node from each list into the heap.
        // We use lists.length + 1 because Java PriorityQueue does not allow
        // initial capacity of 0.
        PriorityQueue<ListNode> minElements = new PriorityQueue(lists.length + 1, new ListNodeComparator());
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                minElements.offer(lists[i]);
                lists[i] = lists[i].next;
            }
        }
        // Use the dummy head node to avoid handling the first element
        // differently than the remaining elements.
        ListNode dummyHead = new ListNode(-1);
        ListNode parent = dummyHead;

        // Take the smallest element in the heap, and push its child
        // onto the heap.
        while (minElements.size() != 0) {
            ListNode cur = minElements.poll();
            if (cur.next != null)
                minElements.offer(cur.next);
            parent.next = cur;
            parent = parent.next;
        }
        return dummyHead.next;
    }
}

## Merge Two Sorted Lists
**Python**

# As long as both lists have elements, repeatedly compare their smallest
# elements and move the smaller element to the merged list. When one list is
# exhausted, append the remaining chunk of the remaining list to the merged
# list.
# This algorithm consumes one node from one of the lists at every iteration,
# and performs a constant amount of work to do so. Therefore, the running time
# is O(m + n), where m and n are the lengths of the lists.
class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        dummyHead = ListNode("dummy")
        cur = dummyHead
        while l1 and l2:
            if l1.val < l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        if not l1:
            cur.next = l2
        else:
            cur.next = l1
        return dummyHead.next

**Java**

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 0 is an arbitrary value here
        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        if (l1 == null)
            cur.next = l2;
        else
            cur.next = l1;
        return dummyHead.next;
    }
}

## Remove Duplicates II
**Python**

# The high level idea is to start at some non-duplicate parent node and
# examine its child to determine whether the child is a duplicate. If the child
# is a duplicate, then remove the child and all of its duplicates by pointing
# the parent's next pointer at the first node with a value that does not match
# the original child's value. If the child is not a duplicate, then the child
# becomes the new parent. In order to guarantee that the first parent is not a
# duplicate, we create a dummy head with a value not equal to the original head
# and use that as the initial parent.
# Since this algorithm either advances the parent pointer or eliminates at
# least one child in each iteration, and each iteration takes a constant amount
# of work, it completes in O(n) time.
class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # Attach a dummy head so that duplicate entries at the start don't need
        # to be a special case.
        dummyHead = ListNode("dummy")
        dummyHead.next = head

        parent = dummyHead
        current = parent.next
        while parent and current:
            # No duplicate, advance both pointers.
            if not current.next or current.next.val != current.val:
                parent = current
                current = current.next
                continue

            # There is a duplicate, advance the second pointer until it points
            # to a node with a value different from its previous value.
            val = current.val
            while current and current.val == val:
                current = current.next
            parent.next = current

        return dummyHead.next

**Java**

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        // Attach a dummy head so that duplicate entries at the start don't need
        // to be a special case.
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode parent = dummyHead;
        ListNode current = parent.next;
        while (parent != null && current != null) {
            // No duplicate, advance both pointers.
            if (current.next == null || current.next.val != current.val) {
                parent = current;
                current = current.next;
                continue;
            }
            // There is a duplicate, advance the second pointer until it points
            // to a node with a value different from its previous value.
            int val = current.val;
            while (current != null && current.val == val) {
                current = current.next;
            }
            parent.next = current;
        }
        return dummyHead.next;
    }
}

## Reorder List
**Python**

# The key challenge in writing an efficient solution is figuring out how to
# iterate from both ends of the list at the same time.
# The key insight is to chop the list at the halfway point, and reverse the
# second half of the linked list. Then, one can iterate both lists
# simultaneously and zip them together to achieve the desired reordering.
# Since linked list reversal and traversal are both linear time, the overall
# algorithm is also O(n).

class Solution(object):
    def reverseList(self, head):
        previous = None
        while head:
            next_head = head.next
            head.next = previous
            previous = head
            head = next_head
        return previous

    def getLen(self, head):
        s = 0
        while head:
            head = head.next
            s+=1
        return s

    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: void Do not return anything, modify head in-place instead.
        """
        # Split the list in half and reverse the second half
        halfLength = (self.getLen(head) + 1) / 2
        secondHalf = head
        parent = None
        for _ in xrange(halfLength):
            parent = secondHalf
            secondHalf = secondHalf.next
        secondHalf = self.reverseList(secondHalf)

        # Truncate the first half of the list.
        if parent:
            parent.next = None

        # Zip the two pieces together
        while head and secondHalf:
            nextHead = head.next
            nextSecond = secondHalf.next
            head.next = secondHalf
            secondHalf.next = nextHead
            head = nextHead
            secondHalf = nextSecond

**Java**

class Solution {
    private ListNode reverseList(ListNode head) {
        ListNode previous = null;
        while (head != null) {
            ListNode next_head = head.next;
            head.next = previous;
            previous = head;
            head = next_head;
        }
        return previous;
    }
    private int getLen(ListNode head) {
        int count = 0;
        while (head != null) {
            head = head.next;
            count++;
        }
        return count;
    }

    public void reorderList(ListNode head) {
        // Split the list in half and reverse the second half
        int halfLength = (getLen(head) + 1) / 2;
        ListNode secondHalf = head;
        ListNode parent = null;
        for (int i = 0; i < halfLength; i++) {
            parent = secondHalf;
            secondHalf = secondHalf.next;
        }
        secondHalf = reverseList(secondHalf);

        // Truncate the first half of the list.
        if (parent != null)
            parent.next = null;

        // Zip the two pieces together
        while (head != null && secondHalf != null) {
            ListNode nextHead = head.next;
            ListNode nextSecond = secondHalf.next;
            head.next = secondHalf;
            secondHalf.next = nextHead;
            head = nextHead;
            secondHalf = nextSecond;
        }
    }
}