给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2] 输出：[2,1]
示例 3：
输入：head = [] 输出：[]
提示：
- 链表中节点的数目范围是
[0, 5000] -5000 <= Node.val <= 5000
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
定义指针 p、q 分别指向头节点和下一个节点，pre 指向头节点的前一个节点。
遍历链表，改变指针 p 指向的节点的指向，将其指向 pre 指针指向的节点，即 p.next = pre。然后 pre 指针指向 p，p、q 指针往前走。
当遍历结束后，返回 pre 指针即可。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
previous, current, next = None, head, None
while current is not None:
next = current.next
current.next = previous
previous = current
current = next
return previous迭代版本：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null, p = head;
while (p != null) {
ListNode q = p.next;
p.next = pre;
pre = p;
p = q;
}
return pre;
}
}递归版本：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode res = reverseList(head.next);
head.next.next = head;
head.next = null;
return res;
}
}/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function (head) {
let pre = null;
for (let p = head; p; ) {
let q = p.next;
p.next = pre;
pre = p;
p = q;
}
return pre;
};/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
var pre *ListNode
for p := head; p != nil; {
q := p.Next
p.Next = pre
pre = p
p = q
}
return pre
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = nullptr;
ListNode* p = head;
while (p)
{
ListNode* q = p->next;
p->next = pre;
pre = p;
p = q;
}
return pre;
}
};/**
* Definition for singly-linked list.
* 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 {
public ListNode ReverseList(ListNode head) {
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.
* 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 {
if (head == null) {
return head;
}
let pre = null;
let cur = head;
while (cur != null) {
const next = cur.next;
cur.next = pre;
[pre, cur] = [cur, next];
}
return pre;
}递归：
/**
* Definition for singly-linked list.
* 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)
* }
* }
*/
const rev = (pre: ListNode | null, cur: ListNode | null): ListNode | null => {
if (cur == null) {
return pre;
}
const next = cur.next;
cur.next = pre;
return rev(cur, next);
};
function reverseList(head: ListNode | null): ListNode | null {
if (head == null) {
return head;
}
const next = head.next;
head.next = null;
return rev(head, next);
}循环：
// 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>> {
match head {
None => None,
Some(mut head) => {
let mut cur = head.next.take();
let mut pre = Some(head);
while let Some(mut node) = cur {
let next = node.next.take();
node.next = pre;
pre = Some(node);
cur = next;
}
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 {
fn rev (pre: Option<Box<ListNode>>, cur: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
match cur {
None => pre,
Some(mut node) => {
let next = node.next;
node.next = pre;
Self::rev(Some(node), next)
},
}
}
pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
Self::rev(None, head)
}
}