自己电脑上做网站,唐尧文化 网站建设工作总结,傻瓜式网站简单界面,安远县建设局网站目录
1.反转链表#xff08;leetcode206#xff09;
2. 链表内指定区间反转#xff08;leetcode92#xff09;
3.链表中的节点每k个一组翻转#xff08;leetcode25#xff09;
4.合并两个排序的链表#xff08;leetcode21#xff09;
5.链表的中间节点#xff08…目录
1.反转链表leetcode206
2. 链表内指定区间反转leetcode92
3.链表中的节点每k个一组翻转leetcode25
4.合并两个排序的链表leetcode21
5.链表的中间节点leetcode876
6.重排链表leetcode143
7.旋转链表leetcode61
8.删除排序链表中的重复元素leetcode83
9.删除排序链表中的重复元素LeetCode 82迭代版
10.环形链表 II LeetCode 142
11.回文链表 LeetCode 234
12.相交链表 LeetCode 160
13.奇偶链表 LeetCode 328
14.移除链表元素 LeetCode 203
15.链表题目做题总结 1.反转链表leetcode206 import java.util.*;/** public class ListNode {* int val;* ListNode next null;* public ListNode(int val) {* this.val val;* }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param head ListNode类 * return ListNode类*/public ListNode ReverseList (ListNode head) {// write code hereListNode prevnull;ListNode curhead;if(headnull){return null;}if(head.nextnull){return head;}while(cur!null){ListNode tempcur.next;cur.nextprev;prevcur;curtemp;}return prev;}
} 2. 链表内指定区间反转leetcode92 import java.util.*;/** public class ListNode {* int val;* ListNode next null;* public ListNode(int val) {* this.val val;* }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param head ListNode类 * param m int整型 * param n int整型 * return ListNode类*/public ListNode reverseBetween (ListNode head, int m, int n) {// write code hereListNode dummynew ListNode(0);dummy.nexthead;ListNode prevdummy;for(int i0;im-1;i){prevprev.next;}ListNode curprev.next;for(int i0;in-m;i){ListNode tempcur.next;cur.nexttemp.next;temp.nextprev.next;prev.nexttemp;}return dummy.next;}
}
3.链表中的节点每k个一组翻转leetcode25 public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param head ListNode类* param k int整型* return ListNode类*/public ListNode reverseKeyGroup (ListNode head, int k) {// write code hereListNode tailhead;//1.递归结束的点for (int i 0; i k; i) {if(tailnull){return head;}tailtail.next;}//2.完成每k个元素内的翻转ListNode prevnull;ListNode curhead;while (cur!tail){ListNode tempcur.next;cur.nextprev;prevcur;curtemp;}head.nextreverseKeyGroup(tail,k);return prev;}
}
4.合并两个排序的链表leetcode21 import java.util.*;/** public class ListNode {* int val;* ListNode next null;* public ListNode(int val) {* this.val val;* }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param pHead1 ListNode类 * param pHead2 ListNode类 * return ListNode类*/public ListNode Merge (ListNode pHead1, ListNode pHead2) {// write code hereListNode dummy new ListNode(-1);ListNode prevdummy;while(pHead1!null pHead2!null){if(pHead1.valpHead2.val){prev.nextpHead1;pHead1pHead1.next;prevprev.next;}else{prev.nextpHead2;pHead2pHead2.next;prevprev.next;}}if(pHead1!null){prev.nextpHead1;}if(pHead2!null){prev.nextpHead2;}return dummy.next;}
}
5.链表的中间节点leetcode876 解题快慢指针 class Solution {public ListNode middleNode(ListNode head) {ListNode fasthead;ListNode slowhead;while(fast!null fast.next!null){slowslow.next;fastfast.next.next;}return slow;}
}6.重排链表leetcode143
给定一个单链表 L 的头节点 head 单链表 L 表示为
L0 → L1 → … → Ln - 1 → Ln请将其重新排列后变为
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值而是需要实际的进行节点交换。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public void reorderList(ListNode head) {//1.快慢指针找到中间节点分成左右两个链表ListNode leftHeadhead;ListNode midmidNode(head);ListNode rightHeadmid.next;//断开左右两个链表mid.nextnull;//2.反转右边的链表rightHeadreverse(rightHead);//3.交错合并左右链表while(leftHead!null rightHead!null){ListNode leftHeadNextleftHead.next;ListNode rightHeadNextrightHead.next;leftHead.nextrightHead;leftHeadleftHeadNext;rightHead.nextleftHead;rightHeadrightHeadNext;}}public ListNode midNode(ListNode head){ListNode slowhead;ListNode fasthead;while(fast!null fast.next!null){fastfast.next.next;slowslow.next;}return slow;}public ListNode reverse(ListNode head){ListNode prevnull;ListNode curhead;if(headnull){return null;}if(head.nextnull){return head;}while(cur!null){ListNode tempcur.next;cur.nextprev;prevcur;curtemp;}return prev;}
}
7.旋转链表leetcode61
给你一个链表的头节点 head 旋转链表将链表每个节点向右移动 k 个位置。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode rotateRight(ListNode head, int k) {if(headnull || k0){return head;}//计算出链表的长度当k非常大时走k步等于走k%len步ListNode curhead;int len0;while(cur!null){len1;curcur.next;}kk%len;//former指针先走k步ListNode formerhead;ListNode laterhead;for(int i0;ik;i){formerformer.next;}while(former.next!null){formerformer.next;laterlater.next;}former.nexthead;ListNode newHeadlater.next;later.nextnull;return newHead;}
}
8.删除排序链表中的重复元素leetcode83
给定一个已排序的链表的头 head 删除所有重复的元素使每个元素只出现一次 。返回 已排序的链表 。 class Solution {public ListNode deleteDuplicates(ListNode head) {ListNode curhead;if(headnull || head.nextnull){return head;}while(cur!null cur.next!null){if(cur.valcur.next.val){cur.nextcur.next.next;}else{curcur.next;}}return head;}
9.删除排序链表中的重复元素LeetCode 82迭代版
给定一个已排序的链表的头 head 删除原始链表中所有重复数字的节点只留下不同的数字 。返回 已排序的链表 。 也可以使用递归的方式个人认为迭代的方式更容易理解。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode deleteDuplicates(ListNode head) {ListNode dummynew ListNode(-1);dummy.nexthead;ListNode curdummy;while(cur.next!null cur.next.next!null){if(cur.next.valcur.next.next.val){int valuecur.next.val;while(cur.next!null cur.next.valvalue){cur.nextcur.next.next;}}else{curcur.next;}}return dummy.next;}
}
10.环形链表 II LeetCode 142
给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。
不允许修改 链表。 /*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {ListNode fasthead;ListNode slowhead;while(fast!null fast.next!null){fastfast.next.next;slowslow.next;if(fastslow){ListNode bfast;ListNode ahead;while(a!b){aa.next;bb.next;}return a;}}return null;}
}
11.回文链表 LeetCode 234
给你一个单链表的头节点 head 请你判断该链表是否为
回文链表
。如果是返回 true 否则返回 false 。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public boolean isPalindrome(ListNode head) {if(head.nextnull){return true;}if(head.next.nextnull){if(head.valhead.next.val){return true;}else{return false;}}//1.找到中间节点ListNode fasthead;ListNode slowhead;while(fast.next!null fast.next.next!null){fastfast.next.next;slowslow.next;}//2.分割为两个链表ListNode leftHeadhead;ListNode rightHeadslow.next;//3.反转右边链表rightHead reverse(rightHead);//4.比较左右链表while (rightHead!null){if(leftHead.valrightHead.val){leftHeadleftHead.next;rightHeadrightHead.next;}else{return false;}}return true;}public ListNode reverse(ListNode head){ListNode prenull;ListNode curhead;while(cur!null){ListNode tempcur.next;cur.nextpre;precur;curtemp;}return pre;}
}
12.相交链表 LeetCode 160
给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。
图示两个链表在节点 c1 开始相交 题目数据 保证 整个链式结构中不存在环。
注意函数返回结果后链表必须 保持其原始结构 。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode paheadA;ListNode pbheadB;if(headAnull || headBnull){return null;}while(pa!pb){if(panull){paheadB;}else{papa.next;}if(pbnull){pbheadA;}else{pbpb.next;}}return pa;}
}
13.奇偶链表 LeetCode 328
给定单链表的头节点 head 将所有索引为奇数的节点和索引为偶数的节点分别组合在一起然后返回重新排序的列表。
第一个节点的索引被认为是 奇数 第二个节点的索引为 偶数 以此类推。
请注意偶数组和奇数组内部的相对顺序应该与输入时保持一致。
你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode oddEvenList(ListNode head) {//链表为空或者只有一个节点直接返回即可if(headnull || head.nextnull){return head;}ListNode oddhead;ListNode evenodd.next;ListNode evenHeadeven;while(even!null even.next!null){odd.nexteven.next; oddodd.next;even.nextodd.next;eveneven.next;}odd.nextevenHead;return head;}
}
14.移除链表元素 LeetCode 203
给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode removeElements(ListNode head, int val) {if(headnull){return null;}ListNode dummynew ListNode(-1);dummy.nexthead;ListNode predummy;ListNode curhead;while(cur!null){if(cur.valval){pre.nextcur.next;}else{precur;}curcur.next;}return dummy.next;}
}
15.链表题目做题总结 1.画图理清思路。 2.考虑边界条件链表问题通常有很多边界条件需要考虑例如空链表、只有一个节点的链表、链表长度为偶数或奇数等等。 3.双指针技巧 快慢指针用于找链表中点、检测环等问题。 双指针一前一后用于逆转链表、找倒数第k个节点等问题。 双指针同向移动用于合并两个有序链表等问题。 4.递归的应用 有些链表问题可以通过递归来简化处理例如逆转链表、检测回文链表等。 5.注意内存管理 如果涉及到链表节点的删除或插入要确保不会造成内存泄漏或者指针丢失。特别是在删除节点时要注意处理好被删除节点的前驱和后继节点的指针关系。 6.利用哨兵节点简化操作 在一些操作中使用哨兵节点dummy node可以简化边界条件的处理特别是在涉及头节点操作时特别有效。
