Today, we are going to reverse a Linked List.

### Reverse a singly linked list.

The question is pretty straightforward. If given an input `1->2->3->4->5->NULL`, you need to return an output `5->4->3->2->1->NULL`.

Without further ado, let's check on the solution:

``````    public ListNode reverseList(ListNode head) {

ListNode prev = null;

while (curr != null){
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}

return prev;
}
``````

Let me explain a little bit. First, we initialize `prev` and `curr` node which references to `null` and `head` respectively.

While the `curr` node is not empty, we use a `temp` node to temporarily hold the next `curr` node. Then, we set the `curr` points back to `prev` node. Lastly, we move both `prev` and `curr` one node forward with `prev` moves to `curr` and `curr` moves to `temp`. Finally, we return the function with the `prev` node (the last non-null node).

Here's a strategy on reversing a linked list: Just like how you would do a swap in array, first you will need to use a temp variable to hold the next value. Then set the next value to be the previous value. Lastly, set the previous value to current value and current value to be the temp value.

#### Follow up: Reverse a linked list from position m to n.

This is a little more challenging than the previous one. First, you need to find out the range of nodes that are needed to reverse, then connect the reversed parts with the original linked list.

``````    public ListNode reverseBetween(ListNode head, int m, int n) {

if (m >= n || head == null) {
}

// initialize dummy node to store the initial head location
ListNode dummy = new ListNode(0);

// move m - 1 steps ahead (move to pre-m position basically)
for(int i = 1; i < m; i++){
return null;
}
}

ListNode nNode = mNode;
ListNode postnNode = mNode.next;

// begin reversing nodes starting from point m to n - 1
for(int i = m; i < n; i++){

if(postnNode == null){
return null;
}
// reversing nodes
ListNode temp = postnNode.next;
postnNode.next = nNode;
nNode = postnNode;
postnNode = temp;

}

// connect the head and tail of reversed nodes
mNode.next = postnNode;
premNode.next = nNode;

// return the initial head position
return dummy.next;
}

``````

I have commented on most of the important lines in the code. Hope this helps! See you in next post!

Post was published on , last updated on .

Like the content? Support the author by paypal.me!