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;
ListNode curr = head;
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) {
return head;
}
// initialize dummy node to store the initial head location
ListNode dummy = new ListNode(0);
dummy.next = head;
// set head to be one node ahead
head = dummy;
// move m - 1 steps ahead (move to pre-m position basically)
for(int i = 1; i < m; i++){
if(head == null){
return null;
}
head = head.next;
}
ListNode premNode = head;
ListNode mNode = head.next;
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!
