每日一练:LeeCode-24. 两两交换链表中的节点 【链表+虚拟头结点】 LeeCode-19. 删除链表的倒数第 N 个结点【链表+虚拟头结点+双指针(快慢)】
- LeeCode-24. 两两交换链表中的节点
- 思路
- 虚拟头结点
- LeeCode-19. 删除链表的倒数第 N 个结点
- 思路
- 双指针
本文是力扣 每日一练:LeeCode-24. 两两交换链表中的节点 【链表+虚拟头结点】 LeeCode-19. 删除链表的倒数第 N 个结点【链表+虚拟头结点+双指针(快慢)】 学习与理解过程,本文仅做学习之用,对本题感兴趣的小伙伴可以出门左拐
LeeCode-24. 两两交换链表中的节点与LeeCode-19. 删除链表的倒数第 N 个结点
LeeCode-24. 两两交换链表中的节点
-
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
示例 1:
输入:head = [1,2,3,4] 输出:[2,1,4,3]
示例 2:
输入:head = [] 输出:[]
示例 3:
输入:head = [1] 输出:[1]
提示:
- 链表中节点的数目在范围 [0, 100] 内
- 0 <= Node.val <= 100
思路
虚拟头结点
解题思路参考代码随想录
class Solution { public ListNode swapPairs(ListNode head) { if(head==null)return head; // 设置一个虚拟头结点 ListNode dummy = new ListNode(-1); dummy.next = head; // 将虚拟头结点指向head,这样方便后面做删除操作 ListNode cur = dummy; ListNode temp; // 临时节点,保存两个节点后面的节点 ListNode firstNode; // 临时节点,保存两个节点之中的第一个节点 ListNode secondNode; // 临时节点,保存两个节点之中的第二个节点 while(cur.next!=null && cur.next.next!=null){ //奇偶数都需要考虑并判断,主要是cur的位置需要明确 temp = cur.next.next.next; firstNode = cur.next; secondNode = cur.next.next; cur.next = secondNode; //1 secondNode.next = firstNode; //2 firstNode.next = temp; //3 cur = firstNode; // cur移动,准备下一轮交换 } return dummy.next; } }
时间复杂度:O(n)
空间复杂度:O(1)
LeeCode-19. 删除链表的倒数第 N 个结点
给你一个链表,删除链表的倒数第 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 <= 30
- 0 <= Node.val <= 100
- 1 <= n <= sz
思路
双指针
如果要删除倒数第n个节点,让fast移动n步,然后让fast和slow同时移动,直到fast指向链表末尾。删掉slow所指向的节点就可以了
参考代码随想录
- 定义fast指针和slow指针,初始值为虚拟头结点,如图:
- fast⾸先⾛n + 1步 ,为什么是n+1呢,因为只有这样同时移动的时候slow才能指向删除节点的上⼀个节点
- fast和slow同时移动,直到fast指向末尾,如题:
- 删除slow指向的下⼀个节点,如图:
代码实现
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(-1); dummy.next = head; ListNode fastNode = dummy; ListNode slowNode = dummy; // 只要快慢指针相差 n 个结点即可 等价于下面注意 for(int i=0;i<=n;i++){ //注意:n+1,fast首先走n + 1步,因为只有这样同时移动的时候slow才能指向删除节点的上一个节点(方便做删除操作) fastNode = fastNode.next; } while(fastNode!=null){ fastNode = fastNode.next; slowNode = slowNode.next; } slowNode.next = slowNode.next.next; return dummy.next; } }
时间复杂度: O(n)
空间复杂度: O(1)
- 删除slow指向的下⼀个节点,如图:
- fast和slow同时移动,直到fast指向末尾,如题:
- fast⾸先⾛n + 1步 ,为什么是n+1呢,因为只有这样同时移动的时候slow才能指向删除节点的上⼀个节点
- 定义fast指针和slow指针,初始值为虚拟头结点,如图:
-
- 双指针