Given the head of a singly linked list, reverse the list, and return the reversed list.
Input list: { a, b, c, d, e }
Output list: { e, d, c, b, a }Principle
Inside an interaction conditioned by a non-null head value, we store the next node in an independent ListNode, then we cut after the head by setting head.next to newHead, update newHead to head (to be the next updated new tail) and finally set head to the stored next ListNode.
Pictorially:
// principle reverse pointing
// 1->2->3->null ::: newHead = null | head = 1->2->3->null:
// store next (2->3->null), cut head (null<-1) take head newHead (null<-1) update head with next (2->3->null)
// (newHead) null<-1 (head) 2->3->null
// store next (3->null), cut head (null<-2) take head newHead (null<-1<-2) update head (3->null)
// null<-1<-2 3->null
// store next (null), cut head (null<-3) take head newHead (null<-1<-2<-3) update head (null)
// null<-1<-2<-3