# Question

Formatted question description: https://leetcode.ca/all/206.html

Easy

## Description

Example:

Input: 1->2->3->4->5->NULL

Output: 5->4->3->2->1->NULL

A linked list can be reversed either iteratively or recursively. Could you implement both?

## Solution

The recursive solution is to do the reverse operation for head.next, and set head.next.next = head and head.next = null.

The iterative solution uses two pointers, prev and curr. Initially, prev is null and curr points to head. Each step, let nextTemp be the next node of curr before reversing curr. Set curr.next = prev. After that, set both prev and curr to the next step (that is, prev = curr and curr = nextTemp). The loop ends when all nodes in the original list are reversed.

# Code

• 

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/

/*
1,2,3,4,5
2,1 prev=2 - 3,4,5 current=3
3,2,1 prev=3 - 4,5 current=4
...
*/
class Solution_oj_iterative {
ListNode prev = null;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
}
class Solution_oj_recursively {
return p;
}
}

class Solution_recursively {

ListNode dummy = new ListNode(0);

reverse(dummy, current);

return dummy.next;
}

private void reverse(ListNode dummy, ListNode current) {

if (current == null) {
return;
}

ListNode oldDummyNext = dummy.next;

dummy.next = current;
current.next = oldDummyNext;

this.reverse(dummy, current);
}
}

class Solution_iteratively {

ListNode dummy = new ListNode(0);

while (current != null) {

ListNode oldDummyNext = dummy.next;

dummy.next = current;
current.next = oldDummyNext; // initial node, oldDummyNext is null, which is what we want, and which is why "// dummy.next = head;" is commented out above

}

return dummy.next;
}
}
}

############

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
ListNode dummy = new ListNode();
while (curr != null) {
ListNode next = curr.next;
curr.next = dummy.next;
dummy.next = curr;
curr = next;
}
return dummy.next;
}
}

• // OJ: https://leetcode.com/problems/reverse-linked-list/
// Time: O(N)
// Space: O(1)
class Solution {
public:
ListNode h;
p->next = h.next;
h.next = p;
}
return h.next;
}
};

• # Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
while p:
q = p.next
p.next = pre
pre = p
p = q
return pre

class Solution:
def reverseList(self, head: ListNode) -> ListNode:
dummy = ListNode()
while curr:
next = curr.next
curr.next = dummy.next
dummy.next = curr
curr = next
return dummy.next

############

# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
def reverseList(self, root):
if not root or not root.next:
return root

ret = self.reverseList(root.next)
root.next.next = root
root.next = None
return ret

pre = None
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre

# iteratively as queue head inserting
"""
:rtype: ListNode
"""
while p:
tmp = dummy.next
dummy.next = p
p = p.next
dummy.next.next = tmp

# easily leads to a circle. Remove current node's next after recursive call.

if p:
else:


• /**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
dummy := &ListNode{}
for curr != nil {
next := curr.Next
curr.Next = dummy.Next
dummy.Next = curr
curr = next
}
return dummy.Next
}

• /**
* class ListNode {
*     val: number
*     next: ListNode | null
*     constructor(val?: number, next?: ListNode | null) {
*         this.val = (val===undefined ? 0 : val)
*         this.next = (next===undefined ? null : next)
*     }
* }
*/

function reverseList(head: ListNode | null): ListNode | null {
}
let pre = null;
while (cur != null) {
const next = cur.next;
cur.next = pre;
[pre, cur] = [cur, next];
}
return pre;
}


• /**
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
* @return {ListNode}
*/
var reverseList = function (head) {
let dummy = new ListNode();
while (curr) {
let next = curr.next;
curr.next = dummy.next;
dummy.next = curr;
curr = next;
}
return dummy.next;
};


• /**
* public class ListNode {
*     public int val;
*     public ListNode next;
*     public ListNode(int val=0, ListNode next=null) {
*         this.val = val;
*         this.next = next;
*     }
* }
*/
public class Solution {
ListNode pre = null;
for (ListNode p = head; p != null;)
{
ListNode t = p.next;
p.next = pre;
pre = p;
p = t;
}
return pre;
}
}

• // Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
None => None,
while let Some(mut node) = cur {
let next = node.next.take();
node.next = pre;
pre = Some(node);
cur = next;
}
pre
}
}
}
}