Linked Lists

Prev: Strings Next: Stacks and Queues

Problems

Unless otherwise stated, each node has a data field and a next field, where the next field of the last node is null.

8.1

Consider two singly linked lists in which each node holds a number. Assume the lists are sorted, i.e., numbers in the lists appear in ascending order within each list. The merge of the two lists is a list consisting of the nodes of the two lists in which numbers appear in ascending order.

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.

Hint: Two sorted arrays can be merged using two indices. For lists, take care when one iterator reaches the end.

Variant: Solve the same problem when the lists are doubly linked.

---

8.2

This problem is concerned with reversing a sublist within a list.

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 $s$th node to the $f$th node, inclusive. The numbering begins at 1, i.e., the head node is the first node. Do not allocate additional nodes.

Hint: Focus on the successor fields which have to be updated.

Variant: Write a function that reverses a singly linked list. The function should use no more than constant storage beyond that needed for the list itself.

Variant: Write a program which takes as input a singly linked list $L$ and a nonnegative integer $k$, and reverses the list $k$ nodes at a time. If the number of nodes $n$ in the list is not a multiple of $k$, leave the last $n\mathrm{mod}k$ nodes unchanged. Do not change the data stored within a node.

---

8.3

Although a linked list is supposed to be a sequence of nodes ending in null, it is possible to create a cycle in a linked list by making the next field of an element reference an earlier node.

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 do not know the length of the list in advance.

Hint: Consider using two iterators, one fast and one slow.

---

8.4

Given two singly linked lists there may be list nodes that are common to both. This may be desirable from the perspective of reducing memory footprint, as in the flyweight pattern, or maintaining a canonical form.

Write a program that takes two cycle-free singly linked lists, and determines if there exists a node that is common to both lists.

Hint: Solve the simple cases first.

---

8.5

Solve Problem 8.4 for the case where the lists may each or both have a cycle. If such a node exists, return a node that appears first when traversing the lists. This node may not be unique. If one node ends in a cycle, the first cycle node encountered when traversing it may be different from the first cycle node encountered when traversing the second list, even though the cycle is the same. In such cases, you may return either of the two nodes.

Hint: Use case analysis. What if both lists have cycles? What if they end in a common cycle? What if one list has cycle and the other does not?

---

8.6

Given a node in a singly linked list, deleting it in $O(1)$ time appears impossible because its predecessor’s next field has to be updated. However, it can be done with one caveat: the node to delete cannot be the last one in the list, and it must be easy to copy the value part of a node.

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

Hint: Instead of deleting the node, can you delete its successor and still achieve the desired configuration?

---

8.7

Without knowing the length of a linked list, it is not trivial to delete the $k$th last element in a singly linked list.

Given a singly linked list and an integer $k$, write a program to remove the $k$th last element from the list. Your algorithm cannot use more than a few words of storage, regardless of the length of the list. In particular, you cannot assume that it is possible to record the length of the list.

Hint: If you know the length of the list, can you find the $k$th last node using two iterators?

---

8.8

This problem is concerned with removing duplicates from a sorted list of integers.

Write a program that takes as input a singly linked list of integers in sorted order, and removes duplicates from it. The list should be sorted.

Hint: Focus on the successor fields which have to be updated.

Variant: Let $m$ be a positive integer and $L$ a sorted singly linked list of integers. For each integer $k$, if $k$ appears more than $m$ times in $L$, remove all nodes from $L$ containing $k$.

---

8.9

This problem is concerned with performing a cyclic right shift on a list.

Write a program that takes as input a singly linked list and a nonnegative integer $k$, and returns the list cyclically shifted to the right by $k$.

Hint: How does this problem differ from rotating an array?

---

8.10

Consider a singly linked list whose nodes are numbered starting at 0. Define the even-odd merge of the list to be the list consisting of the even-numbered nodes followed by the odd-numbered nodes.

Write a program that computes the even-odd merge.

Hint: Use temporary additional storage.

---

8.11

It is straightforward to check whether the sequence stored in an array is a palindrome. However, if this sequence is stored as a singly linked list, the problem of detecting palindromicity becomes more challenging.

Write a program that tests whether a singly linked list is palindromic.

Hint: It is easy if you can traverse the list forwards and backwards simultaneously.

Variant: Solve the same problem when the list is doubly linked and you have pointers to the head and the tail.

---

8.12

For any integer $k$, the pivot of a list of integers with respect to $k$ is that list with its nodes reordered so that all nodes containing keys less than $k$ appear before nodes containing $k$, and all nodes containing keys greater than $k$ appear after the nodes containing $k$.

Implement a function which takes as input a singly linked list and an integer $k$ and performs a pivot of the list with respect to $k$. The relative ordering of nodes that appear before $k$, and after $k$, must remain unchanged; the same must hold for nodes holding keys equal to $k$.

Hint: Form the three regions independently.

---

8.13

A singly linked list whose nodes contain digits can be viewed as an integer, with the least significant digit coming first. Such a representation can be used to represent unbounded integers.

Write a program which takes two singly linked lists of digits, and returns the list corresponding to the sum of the integers they represent. The least significant digit comes first.

Hint: First, solve the problem assuming no pair of corresponding digits sum to more than 9.

Variant: Solve the same problem when integers are represented as lists of digits with the most significant digit coming first.

Answers

8.1

Traverse the two sorted lists with two iterators, always appending the smaller current node to the result and advancing only that iterator. When one list runs out, append the remainder of the other list. A dummy head simplifies the implementation. Because the existing nodes are reused, the running time is $O(n+m)$ and the extra space is $O(1)$.

---

8.2

Walk to the node just before the sublist, then reverse the sublist in place by repeatedly extracting the next node from the unreversed suffix and inserting it at the front of the sublist. This updates only next pointers and does not allocate nodes. The time is dominated by finding the $f$th node, so the running time is $O(f)$.

---

8.3

Use Floyd’s tortoise-and-hare method. Advance one iterator by one node and the other by two. If they never meet, the list is acyclic. If they meet, there is a cycle. After detection, either compute the cycle length and use two iterators offset by that length, or use the standard equivalent reset argument, to locate the first node on the cycle. The running time is $O(n)$ and the extra space is $O(1)$.

---

8.4

If two cycle-free singly linked lists overlap, they must share the same tail node. Compute the lengths of both lists, advance the longer one by the length difference, then walk both lists in tandem until either they meet or both reach null. The first common node is the overlap point. This runs in $O(n)$ time and $O(1)$ space.

---

8.5

Handle cases explicitly.

• If neither list has a cycle, reduce to Problem 8.4.
• If exactly one list has a cycle, they cannot overlap.
• If both have cycles, first determine whether the cycles are the same by walking one cycle and seeing whether the other cycle root appears on it.

If the cycles are disjoint, there is no overlap. If they are the same, then either the overlap happens before the cycle begins or the first common node lies somewhere on the shared cycle. Compare the acyclic stems as in Problem 8.4 up to the cycle roots; if no overlap is found there, either cycle root is an acceptable answer. This takes $O(n+m)$ time and $O(1)$ space.

---

8.6

Copy the data from the successor node into the given node, then bypass the successor by setting the current node’s next pointer to the successor’s next pointer. This effectively deletes the target node, provided it is not the tail. The running time is $O(1)$.

---

8.7

Advance a first iterator by $k$ nodes, then advance both a first and second iterator in tandem. When the first reaches the end, the second is just before the $k$th last node. Using a dummy head avoids edge cases at the real head. Delete the successor of the second iterator. The running time is $O(n)$ and the extra space is $O(1)$.

---

8.8

Because the list is sorted, duplicates appear consecutively. Traverse the list once; for each node, skip over all immediate successors with the same value, then link the current node directly to the next distinct-value node. Each link is traversed at most once, so the running time is $O(n)$ and the extra space is $O(1)$.

---

8.9

First compute the length $n$ and the tail, then reduce the shift by taking $k\mathrm{mod}n$. If the reduced shift is zero, return the original list. Otherwise, connect the tail to the head to form a cycle, advance to the new tail, which is the $(n-k)$th node in the original list, set the next node as the new head, and break the cycle after the new tail. This runs in $O(n)$ time and $O(1)$ space.

---

8.10

Partition the nodes into two chains while traversing the list: one for even-indexed nodes and one for odd-indexed nodes. Keep tail pointers for both chains, alternate appends as you move through the original list, terminate the odd list with null, and then concatenate the even list with the odd list. This uses existing nodes, runs in $O(n)$ time, and uses $O(1)$ extra space.

---

8.11

Use a fast/slow pointer scan to find the midpoint. Reverse the second half of the list in place, then compare the first half with the reversed second half node-by-node. If every compared value matches, the list is palindromic. This gives $O(n)$ time and $O(1)$ extra space. The reversed half can be restored afterward if desired.

---

8.12

Build three stable chains while traversing the list: less than $k$, equal to $k$, and greater than $k$. Append each node to the appropriate chain without creating new nodes, then concatenate the three chains in order. Because nodes are processed once and appended in encounter order, relative ordering within each region is preserved. The running time is $O(n)$ and the extra space is $O(1)$.

---

8.13

Mimic grade-school addition. Traverse both lists together, summing the corresponding digits and a carry, emit a new digit node containing the ones place, and propagate the carry to the next position. When one list ends, continue with the other; if a carry remains after both are exhausted, append one final node. The running time is $O(n+m)$ and the space for the result is $O(\max (n,m))$.