反转链表
206. 反转链表
剑指 Offer 24. 反转链表
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这是一个基础题了，应该能在纸上写出来！！！
class Solution {
public ListNode reverseList(ListNode head) {
// [prev] [curr]1->2->3->4->5
// NULL<-[prev]1 [curr]2->3->4->5
ListNode curr = head;
ListNode prev = null;
while (curr != null) {
// 保存当前节点的下一个节点
ListNode tmp = curr.next;
// 头插法
curr.next = prev;
prev = curr;
// 链表向后移动一节
curr = tmp;
}
return prev;
}
}
92. 反转链表 II
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这个题和反转链表 I 实际上是一样的，只是增加了指定位置约束。
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
// 哨兵节点
// [1] [sentinel]->1[head]->2->3->4->5->NULL, m = 2, n = 4
ListNode sentinel = new ListNode(0);
sentinel.next = head;
// 先将prev节点移动到第m个节点的*头节点*，示例中`m=2,n=4`也就是 `1` 的位置，作为`m-n`区间反转后的头节点
// [2] [sentinel|prev]->1[head]->2->3->4->5->NULL, m = 2, n = 4
ListNode prev = sentinel;
for (int i = 1; i < m; i++) {
prev = prev.next;
}
// [3] [sentinel]->1[head|prev]->2->3->4->5->NULL, m = 2, n = 4
// 反转第 m-n 位置的节点，即2->3->4这一段
// [4] [sentinel]->1[head|prev]->2[curr]->3->4->5->NULL, m = 2, n = 4
// {
// loop
// [5] [sentinel]->1[head|prev]->2[curr]->3[next]->4->5->NULL
// [6] [sentinel]->1[head|prev]->2[curr]->4->5->NULL
// 3[next]->4->5->NULL
// [7] [sentinel]->1[head|prev]->2[curr]->4->5->NULL
// 3[next]->2[curr]->4->5->NULL
// [8] [sentinel]->1[head|prev]->3[next]->2[curr]->4->5->NULL
// }
ListNode curr = prev.next;
for (int i = m; i < n; i++) {
ListNode next = curr.next;
curr.next = next.next;
next.next = prev.next;
prev.next = next;
}
return sentinel.next;
}
}
剑指 Offer 06. 从尾到头打印链表
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2]
输出：[2,3,1]限制：
0 <= 链表长度 <= 10000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public int[] reversePrint(ListNode head) {
// 1. 求链表长度
int length = 0;
ListNode cursor = head;
while (cursor != null) {
cursor = cursor.next;
length++;
}
// 2. 预分配 length 长度的数组作为返回值，利用数组随机访问特性输出结果
int[] array = new int[length];
for (int idx = length -1; idx >= 0; idx++) {
array[idx] = head.val;
head = head.next;
}
return array;
}
}
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
