专做废旧电子电路板配件回收的网站,投资理财产品网站建设,做网站找哪个好,深圳网站建设费用1. 力扣206 : 反转链表
(1). 题 : 图略
给你单链表的头节点 head #xff0c;请你反转链表#xff0c;并返回反转后的链表。示例 1#xff1a;输入#xff1a;head [1,2,3,4,5]
输出#xff1a;[5,4,3,2,1]
示例 2#xff1a;输入#xff1a;head [1,2]
输出#x…1. 力扣206 : 反转链表
(1). 题 : 图略
给你单链表的头节点 head 请你反转链表并返回反转后的链表。示例 1输入head [1,2,3,4,5]
输出[5,4,3,2,1]
示例 2输入head [1,2]
输出[2,1]
示例 3输入head []
输出[]提示链表中节点的数目范围是 [0, 5000]
-5000 Node.val 5000
解法1 :
该解法的空间复杂度比较高(O(n)), 因为借助了int[n]大小的数组.但空间换时间, 该解法的时间复杂度较低(O(n)).只有for一层循环.
思路 : 首先遍历链表得到链表节点的个数借助数组存储原链表的节点的数据域再for循环覆盖原链表的节点的数据域.
解 :
class Solution {public ListNode reverseList(ListNode head) {ListNode p;int count 0;for (p head; p ! null; p p.next) {count;}int newCount count;int[] arr new int[count];count 0;for (p head; p ! null; p p.next) {arr[count] p.val; }count 0;for (p head; p ! null; p p.next) {p.val arr[newCount - 1];newCount--;}return head;}
}
解法2 : 可以使用递归来解决.以示例1为例.
思路 : 不断递归, 当递归到head指向节点5时(最后一个节点), 返回节点5, last指向节点5, 此时head指向节点4, 将节点5指向节点4, 节点4的指针域设置为null, 返回last指针.
解 :
class Solution {public ListNode reverseList(ListNode head) {if (head null || head.next null) {return head;}ListNode last reverseList(head.next);head.next.next head;head.next null;return last;}
}
解法3 : 迭代双指针
思路 : n1初始时指向空o1记录头节点的下一个节点不断将原链表的节点头插到空链表中并更新n1使得其指向该链表的头节点.
解法 :
class Solution {public ListNode reverseList(ListNode head) {if (head null) {return head;}ListNode n1 null;while (head ! null) {ListNode o1 head.next;head.next n1;n1 head;head o1;}return n1;}
}
2. 力扣203 : 移除链表元素
题 : 图略
给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。示例 1输入head [1,2,6,3,4,5,6], val 6
输出[1,2,3,4,5]
示例 2输入head [], val 1
输出[]
示例 3输入head [7,7,7,7], val 7
输出[]提示列表中的节点数目在范围 [0, 104] 内
1 Node.val 50
0 val 50
解法1 : 迭代
思路 : 增加哨兵节点, 使得处理头节点变得简单.想要删除一个节点, 得找到想要删除节点的上一个节点, 从哨兵节点开始, 如果其下一个节点的数据域为val, 则删除, 否则将指针移到下一个节点.
解 :
class Solution {public ListNode removeElements(ListNode head, int val) {//增加头节点if (head null) {return null;} //哨兵节点ListNode dummy new ListNode(0);dummy.next head;ListNode temp dummy;while (temp.next ! null) {if (temp.next.val val) {temp.next temp.next.next;} else {temp temp.next;}}return dummy.next;}
}
解法2 : 递归
思路 : 基线条件如果head为null则返回null.如果我(当前head所在节点)的数据域与val相等则返回我的下一个节点的递归结果.如果我的数据域与val不想等则返回我与我的下一个节点的递归结果.
解 :
class Solution {public ListNode removeElements(ListNode head, int val) {if (head null) {return head;}//如果我与val相等, 返回下一个节点的递归结果if (head.val val) {return removeElements(head.next, val);} else {//如果我与val不相等, 则返回我以及我的下一个节点的递归结果head.next removeElements(head.next, val);return head;}}
}
3. 力扣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进阶你能尝试使用一趟扫描实现吗
解法1 : 双指针(快慢指针)
注 : 题目中n是合法的, 所以无需考虑n不合法的情况.
思路 : 设置哨兵节点, 为了方便删除头节点的操作.初始时, 快慢指针均指向哨兵节点, fast指针先动,然后快慢指针一起移动, 当fast指针指向最后一个节点时, slow指针刚好指针待删除节点的上一个节点.
解 :
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {//设置哨兵节点ListNode dummy new ListNode(0);dummy.next head;ListNode fast dummy;ListNode slow dummy;while (n-- 0) {fast fast.next;}while (fast.next ! null) {fast fast.next;slow slow.next;}slow.next slow.next.next;return dummy.next;}
}
解法2 : 递归
思路 : 当p为null时, 返回0, t0(此时p指向倒数第一个节点), 返回1, 即倒数第几个节点就返回几而此时p指向该倒数节点的上一个节点所以可以对要删除的节点进行删除操作.
解 :
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {//设置哨兵节点ListNode dummy new ListNode(0, head);recursion(dummy, n);return dummy.next;}public int recursion(ListNode p, int n){if (p null) {return 0;}int t recursion(p.next, n);if (t n) {p.next p.next.next;}return t 1;}
}
