Linked List in Maximal Scoring Subsequences Algorithm
What element would operate as the head of the linked list in this case?


That's of course $L_{k-1}$.

If you are surprised why this works in $O(n)$, that paper has already explained:


  Once a list element has been by-passed by this chain, it will be examined again only if it is being deleted from the list, either in Step 2 or Step 4. The work done in the “reconsider” loop of Step 4 can be amortized over the list item(s) being deleted. Hence, in effect, each list item is examined a bounded number of times, and the total running time is linear.




Let's consider the example given in the paper. The sequence is $(4, -5, 3, -3, 1, 2, -2, 2, -2, 1, 5)$. The list is initially empty. The first subsequence $(4)$ comes, we keep a pointer to the head of the list, like

H &lt;- (4)


Next, we sWe add it to the end of the list. We search $I_1$ and find $L_1&gt;L_2$, so we keep a pointer to the head, like

H &lt;- (4)  (3)
^         /
 \       /
  -------


Next, we skip $-3$ and the subsequence $(1)$ comes. We search $I_2$ and find $L_2=L_3$. Since $I_2$ points to the head, we assert there is no such $j$ such that $L_j&lt;L_3$ and keep a pointer to the head, like

H &lt;- (4)  (3)  (1)
^         /    /
 \       /    /
  ------------


Next, the subsequence $(2)$ comes. We search $I_3$ and find $L_3&lt;L_4, R_3&lt;R_4$, so we apply step 4 and get (note $I_3$ need to be reconsidered after merging while no change is needed here since it points to the head)

H &lt;- (4)  (3)  (1,2)
^         /    /
 \       /    /
  ------------


Next, we skip $-2$ and the subsequence $(2)$ comes. We search $I_3$ and find $L_3&lt;L_4, R_3=R_4$, so we keep a pointer to $I_3$, like

H &lt;- (4)  (3)  (1,2) &lt;- (2)
^         /    /
 \       /    /
  ------------


Next, we skip $-2$ and the subsequence $(1)$ comes. We search $I_4$ and find $L_4=L_5$, then search $I_3$ and find $L_3&lt;L_5, R_3&gt;R_5$. We keep a pointer to $I_3$, like

H &lt;- (4)  (3)  (1,2) &lt;- (2)  (1)
^         /    /  ^          /
 \       /    /    \        /
  ------------      --------


Next, the last subsequence $(5)$ comes. We search $I_5$ and find $L_5&lt;L_6, R_5&lt;R_6$, then we merge $I_5$ and $I_6$ and get

H &lt;- (4)  (3)  (1,2) &lt;- (2)  (1,5)
^         /    /  ^          /
 \       /    /    \        /
  ------------      --------


Note $I_5$ needs to be reconsidered. Since $I_5$ points to $I_3$, we search $I_3$ first and find $L_3&lt;L_5, R_3&lt;R_5$, so we merge $I_3,I_4,I_5$ and get

H &lt;- (4)  (3)  (1,2,−2,2,−2,1,5)
^         /    / 
 \       /    /  
  ------------      


We then reconsider $I_3$ and no change is needed since it points to the head.