## Question

Skiena Chapter 3: Data Structures

Question 3-2) Write a program to reverse the direction of a singly linked list in O(n) time.

To reverse a linked list, need to hang on to three separate pointers:

• One pointer is the runner, which points to the current node being "fixed" (reversed in place).
• One pointer is the prior, which points to the node that will be behind the runner in the list
• One pointer is the temporary pointer to the rest of the list that is still being processed
```if(size=0):
return
if(size==1):
return
if(size=2) :
runner = head
prior = null
temp = runner.getNext()
runner.setNext(prior)
```

if length is 0, do nothing

if length is 1, do nothing

```runner = head
prev = null
next runner = head.getNext()

while(nextrunner != null)
runner.setNext(prev)
prev = runner
runner = nextrunner
nextrunner = runner.getNext()
list.head = runner
```

## Code

This was implemented in the TLinkedList<T> class, the templated generic linked list type:

```	/** Reverse the entire linked list in O(n) time. */
public void reverse() {
if(this.size==0 || this.size==1) {
return;
}
Node<E> runner = this.head;
Node<E> prev = null;
Node<E> next_runner = this.head.getNext();

while(next_runner!=null){
runner.setNext(prev);
prev = runner;
runner = next_runner;
next_runner = next_runner.getNext();
}
this.head = runner;
}
```

Link to full implementation of TLinkedList class: https://git.charlesreid1.com/cs/java/src/master/lists/linked-lists/TLinkedList.java

## Profiling

Here are the total walltime costs and per operation costs for the remove operation defined in the TLinkedList class above.

Code to make these figures is here: https://git.charlesreid1.com/cs/java/src/master/lists/linked-lists/Timing.java

X Axis: N (number of elements in linked list)

Y Axis: Amortized wall time, microseconds (total walltime / N)

X Axis: N (number of elements in linked list)

Y Axis: Total walltime, ms