Linked Lists

Question 1

Merge two sorted lists l1 and l2

Answer 1

ListNode dummyHead = new ListNode(0);
ListNode current=dummyHead;
while(l1!=null && l2!=null) {
if (l1.val <= l2.val) {
current.next = l1; l1 = l1.next;
} else {
current.next = l2; l2 = l2.next;
}
current = current.next;
}
if (l1 != null) current.next = l1;
else if (l2 != null) current.next = l2;
return dummyHead.next;

Question 2

Given the head of a linked list, return the list after sorting it in ascending order.

Answer 2

if (head==null || head.next == null)
return head;
ListNode middle = middleOfList(head);
ListNode leftHalfSorted = sortList(head);
ListNode rightHalfSorted = sortList(middle);
return mergeLists(leftHalfSorted, rightHalfSorted);

Modify finding the middle to break the two halves of the list

    if (head == null) return null;
    ListNode slow=head, fast=head, previous = null;
    while(fast!= null && fast.next!=null) {
        fast=fast.next.next;
        previous = slow;
        slow=slow.next;
    }
    previous.next = null;
    return slow;

Question 2

Find middle of linked list

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

Answer 2

if (head == null) return null;
ListNode slow=head, fast=head;
while(fast!= null && fast.next!=null) {
fast=fast.next.next;
slow=slow.next;
}
return slow;

Question 3

Merge k sorted lists, given as ListNode[] lists

Answer 3

Idea: merge list0 and list2, store in list2, and so on, then list0 and list2, store in list0, …, return list0 at the end

Implementation:
for(int stepSize=0; stepSize < lists.length; stepSize = 2) {
for(int index=0; index + stepSize < lists.length; index += 2stepSize) {
lists[index] = merge(lists[index], lists[index + stepSize]);
}
}

return lists[0];

Question 4

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random –> Y, then for the corresponding two nodes x and y in the copied list, x.random –> y.

Return the head of the copied linked list.

Answer 4

Maintain a map of node copies: originalNode -> deepCopyNode

Go through the linked list and make the node if it doesnt already exist, make the next.

Creating copies:
private Node createCopy(Node node) {
if (node == null)
return null;
if (copiedNodes.containsKey(node))
return copiedNodes.get(node);
Node copy = new Node(node.val);
copiedNodes.put(node, copy);
return copy;
}

Deep copying:
if (head == null) return null;
Node currentNode = head;
while(currentNode != null) {
Node copyNode = createCopy(currentNode);
copyNode.next = createCopy(currentNode.next);
copyNode.random = createCopy(currentNode.random);
currentNode = currentNode.next;
}
return copiedNodes.get(head);

O(N) time and space

Answer 5

Use fast and slow pointers. Slow pointer when fast pointer becomes null (beyond the tail) contains our middle.

    ListNode fast=head, slow = head;
    while(fast!=null && fast.next!=null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;