链表-02
1. 反转链表 II
给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。
真题点击此处:92. 反转链表 II
解题思路:
创建一个虚拟头结点 dummy,并将其指向给定链表的头结点 head,这样可以方便处理特定区间在链表开头的情况。
使用指针 p0 指向待反转区间的前一个节点,初始时指向虚拟头结点 dummy。
将指针 p0 移动到待反转区间的起始位置,即移动 left - 1 次。
初始化两个指针 pre 和 curr,分别表示反转部分的前一个节点和当前节点,初始时 pre 为 nullptr,curr 指向 p0->next。
开始反转操作:遍历需要反转的区间(共 right - left + 1 个节点),每次将当前节点指向前一个节点,更新 pre、curr 和 nxt 指针。
在反转过程中,需要保存下一个节点的指针,以便后续操作。
反转完成后,调整指针连接关系:将反转部分的头结点的 next 指针指向未反转部分的头结点,将 p0 的 next 指针指向反转部分的尾节点。
返回虚拟头结点的 next 指针,即为反转后的链表头。
以下为代码的具体实现:
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode *dummy = new ListNode(0, head);
ListNode *p0 = dummy;
for(int i = 0; i < left - 1; i++){
p0 = p0->next;
}
ListNode *pre = nullptr;
ListNode *curr = p0->next;
for(int i = 0; i < right - left + 1; i++){
ListNode *nxt = curr->next;
curr->next = pre;
pre = curr;
curr = nxt;
}
p0->next->next = curr;
p0->next = pre;
return dummy->next;
}
};
时间复杂度:O(N),其中 NNN 是链表总节点数。最坏情况下,需要遍历整个链表。
空间复杂度:O(1)。只使用到常数个变量。
2. 两数相加 II
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外,这两个数字都不会以零开头。
真题点击此处:445. 两数相加 II
解题思路:
- 反转链表l1。
- 反转链表l2.
- 调用两数相加代码,得到链表l3.
- 反转链表l3即为答案.
以下为具体代码实现:
class Solution {
ListNode *reverseList(ListNode *head) {
if (head == nullptr || head->next == nullptr)
return head;
auto new_head = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return new_head;
}
ListNode *addTwo(ListNode *l1, ListNode *l2, int carry = 0) {
if (l1 == nullptr && l2 == nullptr);
return carry ? new ListNode(carry) : nullptr;
if (l1 == nullptr)
swap(l1, l2);
carry += l1->val + (l2 ? l2->val : 0);
l1->val = carry % 10;
l1->next = addTwo(l1->next, (l2 ? l2->next : nullptr), carry / 10);
return l1;
}
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
l1 = reverseList(l1);
l2 = reverseList(l2);
auto l3 = addTwo(l1, l2);
return reverseList(l3);
}
};
时间复杂度:O(n),其中 n 为 l1长度和 l2长度的最大值。
空间复杂度:O(n)。递归需要 O(n) 的栈空间。
3. K 个一组翻转链表
给你链表的头节点 head ,每 k 个节点一组进行翻转,请你返回修改后的链表。
k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。
真题点击此处:25. K 个一组翻转链表
解题思路:
统计链表的长度 n,通过遍历链表并累加计数器实现。这一步是为了确定要进行多少次反转操作。
创建一个虚拟头结点 dummy,并将其指向给定链表的头结点 head,这样可以方便处理特定区间在链表开头的情况。
使用指针 p0 指向当前待反转区间的前一个节点,初始时指向虚拟头结点 dummy。
初始化两个指针 pre 和 curr,分别表示反转部分的前一个节点和当前节点,初始时 pre 为 None,curr 指向 p0.next。
进行循环,每次反转 k 个节点,直到剩余节点数量不足 k 个。
在每一次的反转操作中,使用循环遍历 k 个节点,并利用指针操作将它们反转。
在反转过程中,需要保存下一个节点的指针,以便后续操作。
反转完成后,调整指针连接关系:将反转部分的尾节点的 next 指针指向下一个待反转区间的头结点,将 p0 的 next 指针指向反转部分的头节点。
更新 p0 指针,继续下一次反转操作。
返回虚拟头结点的 next 指针,即为反转后的链表头。
以下为代码实现:
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
n = 0
count = head
while count:
count = count.next
n += 1
dummy = ListNode(next = head)
p0 = dummy
pre = None
curr = p0.next
while n >= k:
n -= k
for _ in range(k):
nxt = curr.next
curr.next = pre
pre = curr
curr = nxt
nxt = p0.next
p0.next.next = curr
p0.next = pre
p0 = nxt
return dummy.next
时间复杂度:O(n),其中 n 为链表的长度。head 指针会在 O(⌊n/k⌋)个节点上停留,每次停留需要进行一次 O(k) 的翻转操作。
空间复杂度:O(1),我们只需要建立常数个变量。