当前位置:   article > 正文

【Leetcode学习笔记】链表_c#链表的val

c#链表的val

一、链表

1.1 链表的基本结构

链表,是由众多的节点组成,每一个节点包括val和next两个内容。其中val是该节点的值,next是指向下一个节点的指针。

  1. class ListNode {
  2. int val;
  3. ListNode next;
  4. ListNode(int x) {
  5. val = x;
  6. next = null;
  7. }
  8. }
  • 链表可“合”不可“分”:两个链表可能相交,也就是两个不同的节点可能拥有相同的next;但是,一个节点的后方不可能分出两个分支来,因为每个节点的后继是唯一的。
  • 链表可能有环:如果某一个节点的后继,是这个节点前面的某一个节点,那么这个链表就是一个环。

1.2 链表算法题

链表的算法题,几乎全部都是时间复杂度O(n)的,因为你至少需要遍历所有的元素,才能得到结果。但是空间复杂度上,空间复杂度O(1)的方法虽然也是存在的,但是相应的coding难度也会比较大,比较浪费时间。因此,链表题的原则是:

笔试时,要尽可能快的通过所有测试用例,不要关心代码优化;

面试时,要充分的体现自己的算法水平,想办法做代码优化,争取把空间复杂度优化至O(1)。

二、常见链表题的面试解法

2.1 判断链表有没有环

https://leetcode-cn.com/problems/linked-list-cycle-ii/

给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

不允许修改 链表。

例:

输入:head = [3,2,0,-4], pos = 1

输出:返回索引为 1 的链表节点

解释:链表中有一个环,其尾部连接到第二个节点。

分析:我们设头节点为x_0,x_n的后继为x_{n+1}或null。

如果链表有环,设环的长度为m,环的第一个点为x_n(需要return的节点)。那么,整个链表可以写为:

x_0, x_1, ..., {x_n, x_{n+1}, ..., x_{n+m-1} }

我们设置快指针fast和慢指针slow,都指向x_0,然后快指针每次走两步,慢指针每次走一步。直到两个指针相遇,或者快指针遇到null。

如果,快指针遇到了null,说明链表无环,可以直接return null。

如果,两者相遇,我们分析一下两个指针会在哪里相遇。

当慢指针走到x_n时,快指针走到了x_{2n},那么在环内,快指针领先慢指针 n % m 个身位。也就是说,需要再走 m - n % m 步才会相遇,那么相遇的结点就是 x_{n + m - n % m},实际上也就是x_m。那么就只需要再走n步,就到了x_{n+m},即x_n。

怎么控制走n步呢?再把slow指向x_0(head),然后slow和fast一次走一步直至相遇,就是x_n了。

  1. public class Solution {
  2. public ListNode detectCycle(ListNode head) {
  3. if(head == null || head.next == null){return null;}
  4. ListNode slow = head.next, fast = head.next.next;
  5. while(fast != slow){
  6. if(fast == null || fast.next == null){
  7. return null;
  8. }
  9. slow = slow.next;
  10. fast = fast.next.next;
  11. }
  12. fast = head;
  13. while(fast != slow){
  14. fast = fast.next;
  15. slow = slow.next;
  16. }
  17. return fast;
  18. }
  19. }

2.2 判断一个链表是否为回文结构

https://leetcode-cn.com/problems/palindrome-linked-list/

给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false。

进阶:你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?

分析:简单的做法,就是把链表转化成数组,然后就可以了,但是这样有O(n)的空间复杂度。如果需要O(1)的空间复杂度,就必须要调整链表的结构。具体做法为:

第一步:找到链表的中间节点,可用快慢指针,时间复杂度O(n)并在这个过程中,将中间节点以前的部分reverse。

第二步:比较reverse的前半部分和后半部分是否一致。

  1. class Solution {
  2. public boolean isPalindrome(ListNode head) {
  3. if(head == null && head.next == null){
  4. return true;
  5. }
  6. ListNode fast = head, slow = head;
  7. ListNode pre = null, prepre = null;
  8. while(fast != null && fast.next != null){
  9. pre = slow;
  10. slow = slow.next;
  11. fast = fast.next.next;
  12. // 反转链表
  13. pre.next = prepre;
  14. prepre = pre;
  15. }
  16. // 如果节点数量为奇数,那么后半部分从中间节点的下一个点开始
  17. if(fast != null){
  18. slow = slow.next;
  19. }
  20. while(pre != null && slow != null){
  21. if(pre.val != slow.val){return false;}
  22. pre = pre.next;
  23. slow = slow.next;
  24. }
  25. return true;
  26. }
  27. }

2.3 复制含有随机节点指针的链表

https://leetcode-cn.com/problems/copy-list-with-random-pointer/

给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y 。

返回复制链表的头节点。

分析:简单的写法是,定义一个map,key是原节点,value是复制出来的新节点,再根据key的对应关系,还原value的next、random即可。但是这样是有O(n)的空间复杂度。如果需要O(1)的空间,就需要进行以下步骤:

第一步:把链表变成新老交替的结构,复制的节点位于老节点的next。

1->2->3->4->5->null

1->1'->2->2'->3->3'->4->4'->5->5'->null

第二步,根据12345的random,还原1' 2' 3' 4' 5'的random。

第三步,将这个链表拆成两部分,并输出1'->2'->3'->4'->5'->null。

  1. class Solution {
  2. public Node copyRandomList(Node head) {
  3. if(head == null){return null;}
  4. Node p = head;
  5. Node q = head.next;
  6. while(p != null){
  7. Node temp = new Node(p.val);
  8. p.next = temp;
  9. temp.next = q;
  10. p = q;
  11. if(p != null){q = q.next;}
  12. }
  13. p = head;
  14. q = head.next;
  15. while(p != null){
  16. if(p.random != null){q.random = p.random.next;}
  17. p = p.next.next;
  18. if(p != null){q = p.next;}
  19. }
  20. Node newhead = head.next;
  21. p = head;
  22. while(p != null){
  23. q = p.next;
  24. p.next = q.next;
  25. p = p.next;
  26. if(p != null){q.next = p.next;}
  27. }
  28. return newhead;
  29. }
  30. }

2.4 两个链表判断是否相交,并给出相交节点

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。

题目数据 保证 整个链式结构中不存在环。

注意,函数返回结果后,链表必须保持其原始结构

分析:先分别计算两个链表的长度,然后长度大的链表,头节点向后移动差值个位置。随后两个节点一起向前走,直到相遇(相交,返回该节点)或者遇到null(不相交)。

  1. public class Solution {
  2. public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  3. if(headA == null || headB == null){return null;}
  4. ListNode p = headA, q = headB;
  5. int l1 = 0, l2 = 0;
  6. while(p != null){
  7. p = p.next;
  8. l1 += 1;
  9. }
  10. while(q != null){
  11. q = q.next;
  12. l2 += 1;
  13. }
  14. p = headA;
  15. q = headB;
  16. if(l1 > l2){
  17. for(int i = 1; i <= l1 - l2; i++){p = p.next;}
  18. }
  19. if(l2 > l1){
  20. for(int i = 1; i <= l2 - l1; i++){q = q.next;}
  21. }
  22. while(p != null){
  23. if (p == q){return p;}
  24. p = p.next;
  25. q = q.next;
  26. }
  27. return null;
  28. }
  29. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/IT小白/article/detail/618134
推荐阅读
相关标签
  

闽ICP备14008679号