Linked Lists

Question 1

Implementing a basic list API - search, insert, delete - for singly linked lists. Time complexity for search, insert, delete ?

Answer 1

//Search public static ListNode searchList(ListNode L, int key) { while (L != null && L.data != key) { L = L.next; } // If key was not present in the list, L will have become null. return L; } // Insert newNode after node. public static void insertAfter(ListNode node, ListNode newNode) { newNode.next = node.next; node.next = newNode; } // Delete the node immediately following aNode. Assumes aNode is not a tail. public static void deleteList(ListNode aNode) { aNode.next = aNode.next.next; } Search O(n) insert, delete O(1)

Question 2

Updating a mutable string from the 1. front 2. back is slow

Answer 2

1. front

Question 3

Consider using ? to avoid having to check for empty lists.

Answer 3

dummy head

Question 4

Algorithm operating on singly linked lists often benefits from using ?

Answer 4

two iterations, one ahead of the other, or one advancing quicker than the other.

Question 5

Write a program that takes two lists, assumed to be sorted, and returns their merge. The only field your program can change in a node is its next field. Time O(n + m) Space O(1)

Answer 5

public static ListNode mergeTwoSortedLists(ListNode L1, ListNode L2) { // Creates a placeholder for the result. ListNode dummyHead = new ListNode<>(0, null); ListNode current = dummyHead; while (L1 != null && L2 != null) { if (L1.data <= L2.data) { current.next = L1; L1 = L1.next; } else { current.next = L2; L2 = L2.next; } current = current.next; } // Appends the remaining nodes of L1 or L2. current.next = L1 != null ? L1 : L2; return dummyHead.next; }

Question 6

Write a program which takes a singly linked list L and two integers s and f as arguments, and reverses the order of the nodes from the sth node to fth node, inclusive. The numbering begins as 1, i.e., the head node is the first node. Do not allocate additional nodes.

Answer 6

public class ReverseSublist { @EpiTest(testDataFile = “reverse_sublist.tsv”) public static ListNode reverseSublist(ListNode L, int start, int finish) { ListNode dummyHead = new ListNode<>(0, L); ListNode sublistHead = dummyHead; int k = 1; while (k++ < start) { sublistHead = sublistHead.next; } // Reverse sublist. ListNode sublistIter = sublistHead.next; while (start++ < finish) { ListNode temp = sublistIter.next; sublistIter.next = temp.next; temp.next = sublistHead.next; sublistHead.next = temp; } return dummyHead.next; }

Question 7

Write a program that takes the head of a singly linked list and returns null if there does not exist a cycle, and the node at the start of the cycle, if a cycle is present.( You don’t know the length of the list in advance)

Answer 7

public static ListNode hasCycle(ListNode head) { ListNode fast = head, slow = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { // There is a cycle, so now let’s calculate the cycle length. int cycleLen = 0; do { ++cycleLen; fast = fast.next; } while (slow != fast); // Finds the start of the cycle. ListNode cycleLenAdvancedIter = head; // cycleLenAdvancedIter pointer advances cycleLen first. while (cycleLen– > 0) { cycleLenAdvancedIter = cycleLenAdvancedIter.next; } ListNode iter = head; // Both iterators advance in tandem. while (iter != cycleLenAdvancedIter) { iter = iter.next; cycleLenAdvancedIter = cycleLenAdvancedIter.next; } return iter; // iter is the start of cycle. } } return null; // no cycle. } Time O(F) + O(C) = O(n) - O(F) for both pointers to reach the cycle. and O(C) for them to overlap once the slower one enters the cycle.

Question 8

Write a program that takes two cycle-free singly linked lists and determines if there exists a node that is common to both lists. Time O(n) Space O(1)

Answer 8

public static ListNode overlappingNoCycleLists(ListNode l0, ListNode l1) { int l0Length = length(l0), l1Length = length(l1); // Advances the longer list to get equal length lists. if (l0Length > l1Length) { l0 = advanceListByK(l0Length - l1Length, l0); } else { l1 = advanceListByK(l1Length - l0Length, l1); } while (l0 != null && l1 != null && l0 != l1) { l0 = l0.next; l1 = l1.next; } return l0; // nullptr implies there is no overlap between l0 and l1. } public static ListNode advanceListByK(int k, ListNode l) { while (k– > 0) { l = l.next; } return l; } private static int length(ListNode l) { int length = 0; while (l != null) { ++length; l = l.next; } return length; }

Question 9

List problems often have a simple brute-force solution that uses ? space

Answer 9

O(n)

Question 10

Write a program that takes two singly linked lists which may each or both have a cycle. You may return any node that appears in their overlap. Time O(n), n is the total number of nodes in the two input lists Space O(1)

Answer 10

public static ListNode overlappingLists(ListNode l0, ListNode l1) { // Store the start of cycle if any. ListNode root0 = IsListCyclic.hasCycle(l0); ListNode root1 = IsListCyclic.hasCycle(l1); if (root0 == null && root1 == null) { // Both lists don’t have cycles. return DoTerminatedListsOverlap.overlappingNoCycleLists(l0, l1); } else if ((root0 != null && root1 == null) || (root0 == null && root1 != null)) { // One list has cycle, and one list has no cycle. return null; } // Both lists have cycles. ListNode temp = root1; do { temp = temp.next; } while (temp != root0 && temp != root1); return temp == root0 ? root1 : null; }

Question 11

Write a program which deletes a node(not the node after) in a singly linked list. The input node is guaranteed not to be the tail node.

Answer 11

// Assumes nodeToDelete is not tail. public static void deletionFromList(ListNode nodeToDelete) { nodeToDelete.data = nodeToDelete.next.data; nodeToDelete.next = nodeToDelete.next.next; }