Reverse Linked List

PROBLEM

Given the head of a singly Linked List, reverse the list, and return the reversed list.

Example1

*Input*: head = [1,2,3,4,5]
*Output*: [5,4,3,2,1]

Example2

*Input*: head = [1,2]
*Output*: [2,1]

Example3

*Input*: head = []
*Output*: []

SOLVING

Steps

  • Create prevNode and nextNode to solve this problem
  • nextNode equal head next N
  • head next equal prevNode H
  • prevNode equal head P
  • head equal nextNode
  • return prevNode

Example1

 P     H    N
 ↓     ↓    ↓
NULL  [1 -> 2 -> 3 -> 4 -> 5 -> NULL]
  • head next equal prevNode
  • head equal next
	 P  H    N
	 ↓  ↓    ↓
[NULL <- 1  2 -> 3 -> 4 -> 5 -> NULL]
  • head next equal prevNode
  • head equal next
	      P    H    N
	      ↓    ↓    ↓
[NULL <- 1 <- 2  3 -> 4 -> 5 -> NULL]
  • head next equal prevNode
  • head equal next
		   P  H    N
		   ↓  ↓    ↓
[NULL <- 1 <- 2 <- 3  4 -> 5 -> NULL]
  • head next equal prevNode
  • head equal next
			P  H    N
			↓  ↓    ↓
[NULL <- 1 <- 2 <- 3 <- 4  5 -> NULL]
  • head next equal prevNode
  • head equal next
			     P   H N
			     ↓   ↓ ↓
[NULL <- 1 <- 2 <- 3 <- 4 <- 5]  NULL]
  • Return prevNode

Code

class Solution {
public:
  ListNode *reverseList(ListNode *head) {
    ListNode *nextNode = nullptr;
    ListNode *prevNode = nullptr;

    while (head) {
      nextNode = head->next;
      head->next = prevNode;
      prevNode = head;
      head = nextNode;
    }
    return prevNode;
  }
};