原题
反转一个单链表。
示例：
输入： 1->2->3->4->5->NULL
输出： 5->4->3->2->1->NULL
进阶：
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
解法
思想
- 迭代（两种解法）
- 双指针
- 旋转前半部分
cur其实就是head
- 双指针
- 递归
从最后一个节点开始回溯，将箭头倒置。
代码
迭代：
- 双指针(作者：王尼玛)
class Solution {
public ListNode reverseList(ListNode head) {
//申请节点，pre和 cur，pre指向null
ListNode pre = null;
ListNode cur = head;
ListNode tmp = null;
while(cur!=null) {
//记录当前节点的下一个节点
tmp = cur.next;
//然后将当前节点指向pre
cur.next = pre;
//pre和cur节点都前进一位
pre = cur;
cur = tmp;
}
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) {
ListNode newHead = head;
ListNode cur = head;
if(head == null) return null;
while(cur.next != null){
//记录不动的节点
ListNode follow = cur.next.next;
//前半部分连成环
cur.next.next = newHead;
newHead = cur.next;
//将cur连到后半部分上
cur.next = follow;
}
return newHead;
}
}
递归：
/**
* 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 node = reverseList(head.next);
//将head和head.next之间的箭头反转
head.next.next = head;
head.next = null;
return node;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode206-%e5%8f%8d%e8%bd%ac%e9%93%be%e8%a1%a8/
相关推荐
-
leetcode23-合并K个排序链表
原题 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入： [ 1->4->5, 1->3->4, 2->6 ] 输出： 1->1->2->3->...
-
leetcode739-每日温度
原题 根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。 例如，给定一个列表 te...
-
leetcode19-删除链表的倒数第N个节点
原题 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为...
-
leetcode295-数据流的中位数
原题 中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。 例如， [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2....
-
leetcode123-买卖股票的最佳时机III
原题 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意: 你不能同时参与多笔交易（你...
-
leetcode118-杨辉三角
原题 给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。在杨辉三角中，每个数是它左上方和右上方的数的和。 示例: 输入: 5 输出: [ [1], [1,1]...
-
leetcode106-从中序与后序遍历序列构造二叉树
原题 根据一棵树的中序遍历与后序遍历构造二叉树。 注意:你可以假设树中没有重复的元素。 例如，给出 中序遍历 inorder = [9,3,15,20,7] 后序遍历 postor...
-
leetcode78-子集
原题 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。 说明： 解集不能包含重复的子集。 示例: 输入: nums = [1,2,3] 输出: [ [3...
-
leetcode55-跳跃游戏
原题 原题 给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。 示例1: 输入： [2,3,1...