206. 反转链表
一、题目
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
二、遇到的问题
1. 双指针应该设置哪两个指针?
前指针 pre,和当前指针 cur。双指针不意味着代码中只能有两个指针,在某些情况下,可能会使用更多的指针来解决特定的问题。
2. 当 cur 指向 pre 后,如何让 cur 指向下一个 cur?
设置 ListNode temp = cur.next; 先将下一个 cur 保存起来。文章来源:https://www.toymoban.com/news/detail-490082.html
3. 递归方法(需要单独定义)
作用:用来实现递归操作
参数:cur、pre
如何写递归方法:
1. 明确边界条件:当 cur == null 时
2. 如何递归调用方法 return reverse(cur, pre);文章来源地址https://www.toymoban.com/news/detail-490082.html
三、代码
1. 双指针
public class Solution {
/**
* 双指针法
*
* @param head
* @return
*/
public ListNode reverseList(ListNode head) {
ListNode cur = head;
ListNode pre = null;
while (cur != null) {
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
}
class ListNode {
int val;
ListNode next;
public ListNode() {
}
public ListNode(int val) {
this.val = val;
}
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
2. 递归
public class Solution {
/**
* 递归算法
*
* @param head
* @return
*/
public ListNode reverseList1(ListNode head) {
// 递归调用,初始的 cur 就是 head,初始的 pre 就是 null
return reverse(head, null);
}
// 递归方法
public ListNode reverse(ListNode cur, ListNode pre) {
// 退出条件
if (cur == null) {
return pre;
}
// 每个节点都需要递归执行的操作
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
// 递归体
return reverse(cur, pre);
}
}
class ListNode {
int val;
ListNode next;
public ListNode() {
}
public ListNode(int val) {
this.val = val;
}
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
到了这里,关于第二章 链表_206. 反转链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!