毕业设计做系统跟做网站哪个容易,网站开发运营,app生成下载链接,百度统计wordpress移除链表元素
题目连接#xff1a; https://leetcode.cn/problems/remove-linked-list-elements/description/ 使用双指针法#xff0c;开始时#xff0c;一个指针指向头节点#xff0c;另一个指针指向头节点的下一个结点#xff0c;然后开始遍历链表删除结点。
这里要注…移除链表元素
题目连接 https://leetcode.cn/problems/remove-linked-list-elements/description/ 使用双指针法开始时一个指针指向头节点另一个指针指向头节点的下一个结点然后开始遍历链表删除结点。
这里要注意如果是空链表的话使用双指针第二个指针会发生空指针异常所以要判断一下
最后程序运行到最后我们还差头节点没有判断最后加上即可。
class Solution {public ListNode removeElements(ListNode head, int val) {if(head null) {return head;}ListNode prev head;ListNode cur head.next;while(cur ! null) {if(cur.val val) {prev.next cur.next;} else {prev cur;}cur cur.next;}if(head.val val) {head head.next;}return head;}
}反转链表
题目连接 https://leetcode.cn/problems/reverse-linked-list/description/ 我们还是使用双指针不过这次有一个指针就是头指针因为反转链表之后的头指针会发生改变那还不如直接让头指针一起移动先将另一个指针指向头指针的下一个结点然后开始遍历链表把每一个结点的指针指向的对象变为前面的对象。
class Solution {public ListNode reverseList(ListNode head) {if(head null) {return head;}ListNode cur head.next;head.next null;while(cur ! null) {ListNode tmp cur.next;cur.next head;head cur;cur tmp;}return head;}
}链表的中间结点
题目链接 https://leetcode.cn/problems/middle-of-the-linked-list/description/ 使用快慢指针快指针每次走两步慢指针每次走一步最后慢指针所指向的结点就是 中间结点
原理fast 2slow 总路程 这里要注意循环的结束条件 当fast null 并且 fast.next null时才能进入循环并且 fastnull,要放在前面因为只用fast不是null时才能进行 fast.next 的判断 class Solution {public ListNode middleNode(ListNode head) {ListNode fast head;ListNode slow head;while(fast ! null fast.next ! null) {fast fast.next.next;slow slow.next;}return slow;}
}返回倒数第 k 个节点
题目链接 https://leetcode.cn/problems/kth-node-from-end-of-list-lcci/description/ 还是使用快慢指针先让快指针走 k-1 步然后慢指针和快指针一起走每次走一步最后快指针走到最后一个结点时慢指针所指向的节点就是倒数第 k 个节点。
原理就是让slow和fast的差值j就是k
class Solution {public int kthToLast(ListNode head, int k) {ListNode fast head;ListNode slow head;for(int i0; ik-1; i) {fast fast.next;}while(fast.next ! null) {slow slow.next;fast fast.next;}return slow.val;}
}合并两个有序的链表
题目链接 https://leetcode.cn/problems/merge-two-sorted-lists/description/ 创建一个新的头节点list1和list2开始遍历各自的链表然后比较插入到新链表中最后再看一下哪些链表没有遍历完然后把没有遍历完的链表直接插入即可。
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if(list1 null) {return list2;}if(list2 null) {return list1;}ListNode newHead new ListNode();ListNode cur newHead;while(list1 ! null list2 ! null) {if(list1.val list2.val) {cur.next list1;list1 list1.next;} else {cur.next list2;list2 list2.next;}cur cur.next;}if(list1 ! null) {cur.next list1;}if(list2 ! null) {cur.next list2;}return newHead.next;}
}分割链表
题目链接 https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId8tqId11004rp2ru/activity/ojqru/ta/cracking-the-coding-interview/question-ranking 我们可以将单链表拆成两个链表一个链表存储小于x 的结点另一个链表存储大于等于x 的结点然后将两个链表合并
这里建议使用带头链表也就是我们常说的带哨兵位的链表这个链表最大的好处就是可以避免头插的复杂情况既然使用了哨兵位就要知道最后哨兵位是要被丢弃的。
public class Partition {public ListNode partition(ListNode pHead, int x) {ListNode headA new ListNode(-1);ListNode aLast headA;ListNode headB new ListNode(-1);ListNode bLast headB;ListNode cur pHead;while(cur ! null) {if(cur.val x) {aLast.next cur;aLast aLast.next;} else {bLast.next cur;bLast bLast.next;}cur cur.next;}aLast.next headB.next;bLast.next null;return headA.next;}
}链表的回文结构
题目链接 https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId49tqId29370rp1ru/activity/ojqru/ta/2016test/question-ranking 解题思路 我们可以使用快慢指针来遍历链表找到中间结点然后就可以把后半部分的链表进行反转之后从这个链表头尾结点开始向中间遍历。
易错点 1.链表的结点个数有奇数和偶数两种类型我们需要分别讨论 2.区分奇数个结点还是偶数个结点可以从一开始找完中间结点的时候从fast入手,因为找中间结点的循环结束就是fast最后指向尾节点还是null。 3.要一定要保存好fast的信息因为后面在反转链表的时候fast其实已经发生了改变。
public class PalindromeList {public boolean chkPalindrome(ListNode A) {//如果是空链表返回trueif(A null) {return true;}ListNode slow A;ListNode fast A;//找到中间结点while(fast ! null fast.next ! null) {fast fast.next.next;slow slow.next;}//保存fast的结点信息避免后面反转链表丢失信息boolean isOdd true;//是否是奇数个结点if(fast null) {isOdd false;}//反转后半部分的链表ListNode prev slow;ListNode cur slow.next;while(cur ! null) {ListNode curN cur.next;cur.next prev;prev cur;cur curN;}//前后遍历链表ListNode pA A;ListNode last prev;//偶数个结点if(!isOdd) {while(pA.next ! last) {if(pA.val ! last.val) {return false;}pA pA.next;last last.next;}if(pA.val ! last.val) {return false;}}if (isOdd) { //奇数个结点while(pA ! last) {if(pA.val ! last.val) {return false;}pA pA.next;last last.next;}}return true;}
}相交链表
题目链接 https://leetcode.cn/problems/intersection-of-two-linked-lists/ 由于是相交链表在公共结点之前两个链表可能有一个差值如果我们能找到这个差值让长的链表先走差值不属然后两个链表一起遍历直到相遇到公共结点。
这个差值就是两个链表的长度的差。
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {int lenA 0;int lenB 0;ListNode cur headA;while(cur ! null) {lenA;cur cur.next;}cur headB;while(cur ! null) {lenB;cur cur.next;}int k 0;ListNode pl null;ListNode ps null;if(lenA lenB) {k lenA - lenB;pl headA;ps headB;} else {k lenB - lenA;pl headB;ps headA;}while(k ! 0) {pl pl.next;k--;}while(pl ! ps) {pl pl.next;ps ps.next;}return pl;}
}环形链表
题目链接 https://leetcode.cn/problems/linked-list-cycle/ 这里使用快慢指针快指针一次走两步慢指针一次走一步当快指针运动到fast null 或者 fast .next null 这个条件时说明链表不存在环如果有链表存在环那么快指针就会先进入到环中一直做圆周运动一定会存在某一个时刻快慢指针会相遇这时候返回true即可。
public class Solution {public boolean hasCycle(ListNode head) {ListNode fast head;ListNode slow head;while(fast ! null fast.next ! null) {fast fast.next.next;slow slow.next;if(fast slow) {return true;}} return false;}
}为什么快指针每次走两步慢指针走一步可以 快指针会率先进入环中然后慢指针后晚一点进入环中由于两个指针的速度是每次差一步也就是说两个指针每运动一次二者之间的距离就会缩短1步最后两个指针一定会相遇。 快指针一次走3步走4步…n步行吗 快指针如果每次走三步假设两个指针的位置如下 那二者永远都不会相遇
其他情况由读者自行探讨~~
环形链表Ⅱ 找入口点
题目链接 https://leetcode.cn/problems/linked-list-cycle-ii/description/ 我们还是使用快慢指针来做。
假设起点与入口点的距离为 x 环的周长为 C 慢指针与快指针相遇点离起点的距离为L 慢指针所走的路程为 x L 快指针所走的路程为 x L nC (n为正整数n 1,2,3,4…)
这里解释一下两者的路程计算问题 在慢指针还没有进入口点的时候就已经至少路过一次相遇点所以当慢指针刚刚进入环中的时候快指针最少已经走了一圈最多走了 n 圈。 因为慢指针刚进入环中的时候快指针和它最多相差一个圈的距离并且快指针的速度比慢指针的速度要快所以慢指针是不可能走完一圈的假设慢指针走完一圈那快指针一定走完一圈再多一点所以慢指针在完成一圈之前一定会被追上所以慢指针所走的路程为 x L快指针所走的路程为 x L nC (n为正整数n 1,2,3,4…)中的 nC 是遇到慢指针之前就已经完成好的
当快慢指针在环中相遇时由于快指针的速度是慢指针的速度的两倍所以慢指针的路程是快指针的一半即 2 * (x L) x L nC化简整理得 x L nC 即 x nC - L 推导结论 让一个指针从头开始遍历另一个指针从相遇点开始遍历两个指针每次走一步一定会在入口点相遇。 public class Solution {public ListNode detectCycle(ListNode head) {ListNode slow head;ListNode fast head;while(fast ! null fast.next ! null) {fast fast.next.next;slow slow.next;if(slow fast) {break;}}//没有环if(fast null || fast.next null) {return null;}ListNode meet fast;ListNode str head;while(meet ! str) {meet meet.next;str str.next;}return str;}
}
