TAOCP 2.2.3 Exercise 7

Let the linked list be represented by the pointer `FIRST` to the first node, and assume each node has fields `INFO` and `LINK` as in (3).

taocpmathematicsalgorithmsvolume-1medium

Section 2.2.3: Linked Allocation

Exercise 7. [23] Design an algorithm to "invert" a linked linear list such as (1), that is, to change its links so that the items appear in the opposite order. [If, for example, the list (1) were inverted, we would have FIRST linking to the node containing item 5; that node would link to the one containing item 4; etc.]. Assume that the nodes have the form (3).

Verified: yes
Solve time: 47s

Solution

Let the linked list be represented by the pointer FIRST to the first node, and assume each node has fields INFO and LINK as in (3). The goal is to reverse the list in place, i.e., to produce a list in which the original last node becomes the first, the original penultimate node becomes the second, and so on, without allocating new nodes.

Introduce two auxiliary link variables, PREV and CUR. The variable CUR will traverse the original list, while PREV will always point to the partial inverted list already constructed. Initially, the inverted list is empty, so we set PREV \leftarrow \Lambda.

The inversion can be accomplished by repeatedly moving the head of the remaining list to the front of the partially inverted list. At each step, let CUR point to the current node to be moved. Store NEXT \leftarrow \text{LINK}(CUR) to remember the remainder of the original list. Then set LINK(CUR) \leftarrow PREV, effectively inserting CUR at the front of the inverted list. Finally, advance PREV \leftarrow CUR and CUR \leftarrow NEXT. Repeat until CUR = \Lambda.

This process can be written formally as follows:

  1. PREV \leftarrow \Lambda
  2. CUR \leftarrow FIRST
  3. While CUR \ne \Lambda do:

a. NEXT \leftarrow \text{LINK}(CUR)

b. LINK(CUR) \leftarrow PREV

c. PREV \leftarrow CUR

d. CUR \leftarrow NEXT 4. FIRST \leftarrow PREV

At termination, PREV points to the last node of the original list, which becomes the first node of the inverted list, so setting FIRST \leftarrow PREV completes the inversion.

Verification of correctness: At each iteration, the invariant holds: PREV points to the head of the partially inverted list, and CUR points to the next node of the original list to be processed. Each node is moved exactly once, and no links are lost because NEXT temporarily stores the remainder of the original list. When CUR = \Lambda, all nodes have been inverted, and FIRST correctly points to the new head. This completes the proof. ∎

Step count: Each iteration executes one read of LINK(CUR) into NEXT and one write to LINK(CUR), plus two assignments to PREV and CUR. Thus, for a list of $n$ nodes, there are $4n$ link-variable assignments, plus the initializations PREV \leftarrow \Lambda and CUR \leftarrow FIRST, and the final FIRST \leftarrow PREV.

The algorithm uses no additional storage beyond three link variables (PREV, CUR, NEXT) and performs the inversion in linear time, $O(n)$, which is optimal because each node must be visited at least once.