lc92. 反转链表 II（MD）
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
示例 1：
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
|
示例 2：
输入：head = [5], left = 1, right = 1
输出：[5]
|
提示：
- 链表中节点数目为
n 1 <= n <= 500-500 <= Node.val <= 5001 <= left <= right <= n
进阶： 你可以使用一趟扫描完成反转吗？
如果要实现进阶要求，可以考虑使用双指针
简单来说就是这样
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy;
for (int i = 0; i < left - 1; i++) {
pre = pre.next;
}
ListNode cur = pre.next;
ListNode next = cur;
for (int i = 0; i < right - left; i++) {
next = cur.next;
cur.next = next.next;
next.next = pre.next;
pre.next = next;
}
return dummy.next;
}
}
|
lc19. 删除链表的倒数第N个节点（MD）
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
|
示例 2：
输入：head = [1], n = 1
输出：[]
|
示例 3：
输入：head = [1,2], n = 1
输出：[1]
|
提示：
- 链表中结点的数目为
sz 1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz
**进阶：**你能尝试使用一趟扫描实现吗？
和上一题一样，如果要实现进阶要求，可以用双指针
自行推导一下就可以了。这里解释一下为什么一开始要先做一个循环n次的fast指针移动：此处我们假设链表长度为len，快指针移动的总长度应该为len，如果我们一开始就先进行预处理，先做循环n次的fast指针移动，那么后面快慢指针一起移动的时候就只需要移动len-n次，此时慢指针就正好指到倒数的第n个节点
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = head;
ListNode slow = dummy;
for (int i = 0; i < n; i++) {
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}
|
lc82. 删除排序链表的重复元素 II（MD）
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
示例 1：
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
|
示例 2：
输入：head = [1,1,1,2,3]
输出：[2,3]
|
提示：
- 链表中节点数目在范围
[0, 300] 内 -100 <= Node.val <= 100- 题目数据保证链表已经按升序 排列
如果出现了前一个节点的值等于后一个节点的值，跳过去即可
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode cur = dummy;
while (cur.next != null && cur.next.next != null) {
if (cur.next.val == cur.next.next.val) {
int x = cur.next.val;
while (cur.next != null && cur.next.val == x) {
cur.next = cur.next.next;
}
} else {
cur = cur.next;
}
}
return dummy.next;
}
}
|
lc61. 旋转链表（MD）
给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]
|
示例 2：
输入：head = [0,1,2], k = 4
输出：[2,0,1]
|
提示：
- 链表中节点的数目在范围
[0, 500] 内 -100 <= Node.val <= 1000 <= k <= 2 * 10^9
首先，这种旋转肯定不是简简单单的“旋转”，其实只需要判断旋转后链表的头节点是哪一个节点，然后断开它和上一个节点的联系，然后修改尾节点指向即可
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || k == 0 || head.next == null) {
return head;
}
ListNode iter = head;
int len = 1;
while (iter.next != null) {
len++;
iter = iter.next;
}
int add = len - k % len;
if (add == len) {
return head;
}
iter.next = head;
for (int i = 0; i < add; i++) {
iter = iter.next;
}
ListNode res = iter.next;
iter.next = null;
return res;
}
}
|
lc86. 分隔链表（MD）
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例 1：
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
|
示例 2：
输入：head = [2,1], x = 2
输出：[1,2]
|
提示：
- 链表中节点的数目在范围
[0, 200] 内 -100 <= Node.val <= 100-200 <= x <= 200
先用两个链表分开存，最后把两个链表连接起来
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode small = new ListNode(0);
ListNode smallHead = small;
ListNode large = new ListNode(0);
ListNode largeHead = large;
while (head != null) {
if (head.val < x) {
small.next = head;
small = small.next;
} else {
large.next = head;
large = large.next;
}
head = head.next;
}
large.next = null;
small.next = largeHead.next;
return smallHead.next;
}
}
|
