免费tickle网站,长沙做暑假实践活动网站,平度市建设部网站,好看的网站模版目录 1、移除链表元素
2、反转链表
3、链表的中间结点
4、返回倒数第k个结点 5、合并两个有序链表 1、移除链表元素
习题链接https://leetcode.cn/problems/remove-linked-list-elements/description/ 描述#xff1a;给你一个链表的头节点 head 和一个整数 val #xff…目录 1、移除链表元素
2、反转链表
3、链表的中间结点
4、返回倒数第k个结点 5、合并两个有序链表 1、移除链表元素
习题链接https://leetcode.cn/problems/remove-linked-list-elements/description/ 描述给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。 这道题大家看着是不是十分的眼熟这其实就是我们在讲解无头单向链表时进行的一个方法的模拟实现 首先这道题我们要先进行头节点的判断如果头节点为空就代表链表为空没有数据直接返回null 如果不为空我们要创建两个指针一个指向头结点prev,一个指向头节点的下一个结点cur,然后让cur不断的往前走在走的过程中进行判断如果cur的值不等于我们要删除的值就让prev移动到目前cur的位置之后cur继续走如果cur的值等于我们要删除的数居然prev的后继结点变成此时cur的后继结点以达到删除结点的目的 完整代码
class Solution {public ListNode removeElements(ListNode head, int val) {if(head null){return null;}ListNode cur head.next;ListNode perv head;while(cur ! null){if(cur.val val){perv.next cur.next;}else{perv cur;}cur cur.next;}if(head.val val){head head.next;}return head;}
}
2、反转链表
习题链接https://leetcode.cn/problems/reverse-linked-list/description/
描述给你单链表的头节点 head 请你反转链表并返回反转后的链表。 首先我们依然要进行头结点的判断但是这次我们又加了一个判断因为我们这次是要将一个链表进行反转而当我们的链表只有一个数时进行反转后的链表依旧跟原来一样因此当头节点的下一个为空时即链表只有一个数就直接返回头结点即可。 然后这次我们依然要创建一个指针指向头结点的下一个结点cur,因为这次我们是反转链表我们的头节点将会变成最后一个结点而最后有一个结点是没有后继结点的因此我们要将头节点的后继置为空。 之后我们不断让cur往后走并在循环中创建一个新的指向curN令他指向cur的下一个结点这时我们让cur的下一个结点变成头节点之后在将cur变成头节点然后我们在让cur指针指向curN处而进行新的循环时curN因为cur的改变会往后走一个结点这样就实现了cur的移动和链表的反转。 完整代码
class Solution {public ListNode reverseList(ListNode head) {if(head null){return null;}if(head.next null){return head;}ListNode cur head.next;head.next null;while(cur ! null){ListNode curN cur.next;cur.next head;head cur;cur curN;}return head;}
}
3、链表的中间结点
习题链接https://leetcode.cn/problems/middle-of-the-linked-list/description/描述给你单链表的头结点 head 请你找出并返回链表的中间结点。如果有两个中间结点则返 回第二个中间结点。 在这里我们用到了一个我们在做题时经常会使用到的一个方法快慢指针。 所谓快慢指针其实就是让两个指针以同时移动但他们每次移动的距离是不同的这样就使得两个指针移动速度变得不同。 在这道题里我们使用的就是这种方法首先我们设立两个指针快指针fast和慢指针slow让他们指向头节点。 那么我们该怎样利用这两个指针找到中间结点呢? 我们来上面这两个事例当这两个指针都在头节点时我们让fast指针每次走两步让slow指针每次走一步当fast指针走到链表尽头时即fast为空和fast的下一个结点为空时结束移动这时当我们结束移动后会发现我们的slow指针正处于我们要找的中间结点位置 完整代码
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;}
}
4、返回倒数第k个结点
习题链接https://leetcode.cn/problems/kth-node-from-end-of-list-lcci/description/
描述实现一种算法找出单向链表中倒数第 k 个节点。返回该节点的值。 对于这道题他让我们去求倒数第k个结点的值在这里我们有一种方法来解决这个问题。 首先我们求出这个链表的长度我们再用我们求出的长度减去k这时根据得到的数我们让一个指针从头结点走这个数的步我们会发现最后停下的这个结点值正是倒数第k个结点的值。 完整代码
class Solution {public int kthToLast(ListNode head, int k) {ListNode cur head;int count 0;while(cur ! null){count;cur cur.next;}ListNode fast head;int n count-k;while(n ! 0){fast fast.next;n--;}return fast.val;}
} 5、合并两个有序链表
习题链接https://leetcode.cn/problems/merge-two-sorted-lists/description/描述将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所 有节点组成的。 在这里我们用到了一个我们经常使用的方法创建一个虚拟头结点 在这道题里我们先创建一个虚拟头结点node在创建一个指针tmp指向虚拟头结点 我们发现这道题的要求是将两个升序链表合并为一个新的 升序 链表所以我们需要进行大小的比较因此在这里我们先创建一个循环在循环中进行比较让list1链表的值小于list2时就让tmp的后继变成这时list1然后让list1往后走反之就让tmp的后继变成这时list2然后让list2往后走并且每比较一次就让tmp往后走一步这样就成功实现了大小的比较和两个链表的合并但是这里我们需要注意一点如果有一个链表先走完了我们就可以让另一个链表剩下的值直接链接在tmp后边。最后返回从虚拟头节点的下一个结点返回链表这时的链表就是我们新的 升序 链表 完整代码
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode node new ListNode(-1);ListNode tmp node;while(list1 ! null list2 ! null){if(list1.val list2.val){tmp.next list1;list1 list1.next;}else{tmp.next list2;list2 list2.next;}tmp tmp.next;}if(list1 null){tmp.next list2;}if(list2 null){tmp.next list1;}return node.next;}
}
6、分割链表
习题链接https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId8tqId11004rp2ru/activity/ojqru/ta/cracking-the-coding-interview/question-ranking描述现有一链表的头指针 ListNode* pHead给一定值x编写一段代码将所有小于x的结点排在其余结点之前且不能改变原来的数据顺序返回重新排列后的链表的头指针。 首先我们创建两个虚拟头结点并用两个指针指向他们根据题目意思我们要将所有小于x的数放到一边大于等于的放到另一边并且不改变他们的顺序这样的话我们利用排序肯定是不可以了因此我们利用了虚拟头节点的办法我们将小于x的放到一个链表当中大于等于x的放到另一个链表中最后在让这两个链表链接在一起这样就成功的分割了链表 注意在最后我们要将存放大于等于x的链表最后一个结点的后继如果不等于空就要置为空。 如果小于x 的链表为空我们可以直接返回大于等于x的链表。 完整代码
public class Partition {public ListNode partition(ListNode pHead, int x) {ListNode head1 new ListNode(-1);ListNode head2 new ListNode(-2);ListNode cur head1;ListNode prev head2;ListNode node pHead;while(node ! null){if(node.val x){cur.next node;cur cur.next;}else{prev.next node;prev prev.next;}node node.next;}cur.next head2.next;if(head2.next ! null){prev.next null;}if(head1.next null){return head2.next;}return head1.next;}
}
7、链表的回文结构
习题链接https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId49tqId29370rp1ru/activity/ojqru/ta/2016test/question-ranking
描述对于一个链表请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法判断其是否为回文结构。给定一个链表的头指针A请返回一个bool值代表其是否为回文结构。保证链表长度小于等于900。 根据题意我们直到我们要判断链表是否为回文链表我们当为空和只有一个数时都是回文结构因此要先进行判断之后我直到回文结构代表链表一半和另一半的反转时相同的因此我们发现这时我们上面讲的反转链表和求中间结点的结合所以这题的思路就是找到中间结点讲中间结点和之后的结点进行反转最后在与另一半进行比较每个结点的值如果出现一个不等就代表不是回文结构如果另一个链表的下一个值等于我们反转后最后一个值直接就可以范围true 完整代码
public class PalindromeList {public boolean chkPalindrome(ListNode A) {if(A null || A.next null){return true;}ListNode fast A;ListNode slow A;while(fast ! null fast.next ! null){fast fast.next.next;slow slow.next;}ListNode cur slow.next;while(cur ! null ){ListNode curN cur.next;cur.next slow;slow cur;cur curN;}while(A ! slow){if(A.val ! slow.val){return false;}if(A.next slow){return true;}A A.next;slow slow.next;}return true;}
}
8、相交链表
习题链接https://leetcode.cn/problems/intersection-of-two-linked-lists/
描述给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。 首先我们创建两个指针cur1和cur2令他们分别指向head1和head2,这道题要我们判断两个链表存不存在相交结点但是我们知道这两个可能长度是不相同的这就会导致在他们相交前是不一样长的因此我们要先求出这两个链表的长度差然后让长的链表先走差值步令他们在同一个起跑线上在一步一步的走同时进行判断如果走到最后都没有相等就代表没有相交 完整代码
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode cur1 headA;ListNode cur2 headB;int count1 0;while(cur1 ! null){cur1 cur1.next;count1;}int count2 0;while(cur2 ! null){cur2 cur2.next;count2;}cur1 headA;cur2 headB;int count3 count1-count2;if(count3 0){cur1 headB;cur2 headA;count3 count2 -count1;}while(count3 ! 0){cur1 cur1.next;count3--;}while(cur1 ! cur2){cur1 cur1.next;cur2 cur2.next;}if(cur1 null){//当走到最后链表会为空但这时他们会相等因此跳出循环所以我们要先判 //断是否是走到尽头引起的相等如果是就返回null,如果不是就往下执行truereturn null;}return cur1;}
}
9、环形链表
习题链接https://leetcode.cn/problems/linked-list-cycle/description/描述
给你一个链表的头节点 head 判断链表中是否有环。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 则返回 true 。 否则返回 false 。 这道题利用了快慢指针法根据题意他要判断是否为环形链表如果他是环形的话我们发现如果我们利用快慢指针让一个指针一次走两步一个一次走一步当慢指针进环的时候最好的情况下很快就会相遇最坏的情况下是他们直接的距离是环的长度但因为慢指针一次走一步快指针一次走两步没动一次他们间的距离就会减少一步因此他们一定会相遇所以如果他们相遇就代表有环如果快指针走到最后为空就代表没有环 注意当链表为空和只有一个结点时也是没有环的。 完整代码
public class Solution {public boolean hasCycle(ListNode head) {if(head null || head.next null){return false;}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;}
}
10、环形链表II 习题链接https://leetcode.cn/problems/linked-list-cycle-ii/description/
描述
给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。
不允许修改链表。 这道题让我们去求环的入口点首先我们来看下面这张图 我们知道当我们进行环的判断时会有一个相遇点(M)我们假设入口点(E)到相遇点的距离为x,环的总长为R, 而链表的头结点到入口点的距离为L根据上题我们知道两个指针在相遇前快指针可能已经走了n圈所以快指针走的路程为LxnR慢指针走的路程为Lx而快指针是以慢指针的2倍前进的因此他们相遇时快指针的的路程是慢指针的两倍因此我们得出2*LxLxnR 当我们化简后发现L nR-x,而我们的n取决于fast走的圈数但是当我们以n1来看时我们发现L的长度就等于R-XLR-x是一定的n的形成只是由于指针速度不同所导致的这时我们发现如果有两个指针从头节点和相遇点一起走当他们相遇时的相遇结点就是我们的入口点 完整代码
public class Solution {public ListNode detectCycle(ListNode head) {if(head null || head.next null){return null;}ListNode fast head;ListNode slow head;while(fast ! null fast.next ! null){fast fast.next.next;slow slow.next;if(fast slow){break;}}if(fast null || fast.next null){return null;}fast head;while(fast ! slow){fast fast.next;slow slow.next;}return fast;}
}好了今天的分享就到这里了还请大家多多关注我们下一篇见
