Reverse Linked List

1/**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 *     int val;
5 *     ListNode next;
6 *     ListNode() {}
7 *     ListNode(int val) { this.val = val; }
8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9 * }
10 */
11class Solution {
12    ListNode reverse(ListNode curr, ListNode prev) {
13        if (curr == null) {
14            return prev;
15        }
16        ListNode next = curr.next;
17        curr.next = prev;
18        return reverse(next, curr);
19    }
20
21    public ListNode reverseList(ListNode head) {
22        return reverse(head, null);
23    }
24}
25
26/**
27 * Definition for singly-linked list.
28 * public class ListNode {
29 *     int val;
30 *     ListNode next;
31 *     ListNode() {}
32 *     ListNode(int val) { this.val = val; }
33 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
34 * }
35 */
36// iterative solution
37// time O(n)
38// space O(1)
39// class Solution {
40//     public ListNode reverseList(ListNode head) {
41//         ListNode curr = head;
42//         ListNode prev = null;
43        
44//         while (curr != null) {
45//             ListNode next = curr.next;
46//             curr.next = prev;
47//             prev = curr;
48//             curr = next;
49//         }
50
51//         return prev;
52//     }
53// }

1// Definition for singly-linked list.
2// #[derive(PartialEq, Eq, Clone, Debug)]
3// pub struct ListNode {
4//   pub val: i32,
5//   pub next: Option<Box<ListNode>>
6// }
7// 
8// impl ListNode {
9//   #[inline]
10//   fn new(val: i32) -> Self {
11//     ListNode {
12//       next: None,
13//       val
14//     }
15//   }
16// }
17impl Solution {
18    pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
19        let mut curr = head;
20        let mut prev = None;
21
22        while let Some(mut node) = curr {
23            let mut next = node.next.take();
24            node.next = prev.take();
25            prev = Some(node);
26            curr = next.take();
27        }
28
29        return prev;
30    }
31}