链表经典面试题（含图解）

转x33g5p2x  于2021-11-21 转载在 其他  
字(7.9k)|赞(0)|评价(0)|浏览(352)

一、删除链表中等于给定值 val 的所有节点

对应leetcode题

因为要删除某一个结点，就要遍历到该结点之前的位置。为了记录需要删除的结点的前一位置，我们需要另外创建一个指针pre来记录。先不对头结点进行判断它的val值是否等于val，因此只需将cur设为头结点的后一个结点即可。若先对头指针判断，则可能需要不断地改变头指针，会非常麻烦。因此先遍历整个链表，如果遇到有需要删除的结点，则有pre.next=cur.next；cur=cur.next；否则pre=cur;cur=cur.next;
如果23为需要删除的结点，则有以下的例子：
图解：

遇到需要删除的结点：pre.next=cur.next；cur=cur.next

遇到不需要删除的结点：当cur为空时，则退出循环。遍历结束后还要判断头结点的 值是否等于val。

代码示例：

  1. * public class ListNode {
  2.  *     int val;
  3.  *     ListNode next;
  4.  *     ListNode() {}
  5.  *     ListNode(int val) { this.val = val; }
  6.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  7.  * }
  8.  */
  9. class Solution {
  10.     public ListNode removeElements(ListNode head, int val) {
  11.         if(head==null) {
  12.             return null;
  13.         }
  14.         ListNode cur = head.next;
  15.         ListNode pre = head;
  16.         while(cur!=null) {
  17.             if(cur.val==val) {
  18.                 pre.next=cur.next;
  19.                 cur=cur.next;
  20.             } else {
  21.                 pre=cur;
  22.                 cur=cur.next;
  23.             }
  24.         }
  25.         if(head.val==val) {
  26.             head=head.next;
  27.         }
  28.         return head;
  29.     }
  30. }

二、反转单链表

对应leetcode题
对应如图所示：

为了反转链表，我们需要设置三个引用，因为一个要记录前面的位置pre，一个要记录后面的位置curNext，还有一个要作为链接链表的点cur。因为头结点会随着反转链表的改变而改变，因此要设置一个新的头结点newHead。

代码示例：

  1. * public class ListNode {
  2.  *     int val;
  3.  *     ListNode next;
  4.  *     ListNode() {}
  5.  *     ListNode(int val) { this.val = val; }
  6.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  7.  * }
  8.  */
  9. class Solution {
  10.     public ListNode reverseList(ListNode head) {
  11.         ListNode cur = head;
  12.         ListNode pre = null;
  13.         ListNode curNext = null;
  14.         ListNode newHead = null;
  15.         while(cur!=null) {
  16.             curNext=cur.next;
  17.             if(curNext==null) {
  18.                 newHead=cur;
  19.             }
  20.             cur.next=pre;
  21.             pre=cur;
  22.             cur=curNext;
  23.         }
  24.         return newHead;
  25.     }
  26. }

三、找链表的中间结点

对应leetcode题
寻找中间结点，我们要找到路程与速度的规律。速度两倍的路程也是两倍，因此说明我们可以设置两个指针来走，如果一个指针是另一个指针速度的两倍，当它走到链表尾时，则另一个指针在链表的中间，因此走的慢的那个指针的位置就是中间结点的位置。但是有两种情况：第一种是单链表的结点数为奇数，第二种是单链表的结点数为偶数。

因此有两种情况：结点数为偶数时判断fast.next是否为null，结点数为奇数时判断fast是否为null。当两种情况下只有一种情况满足，则直接返回slow指针即可找到中间结点。

  1. * public class ListNode {
  2.  *     int val;
  3.  *     ListNode next;
  4.  *     ListNode() {}
  5.  *     ListNode(int val) { this.val = val; }
  6.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  7.  * }
  8.  */
  9. class Solution {
  10.     public ListNode middleNode(ListNode head) {
  11.         if(head==null) {
  12.             return null;
  13.         }
  14.         ListNode fast = head;
  15.         ListNode slow = head;
  16.         while(fast!=null&&fast.next!=null) {
  17.             fast=fast.next.next;
  18.             slow=slow.next;
  19.         }
  20.         return slow;
  21.     }
  22. }

四、找链表中的第k个结点

对应leetcode题
我们用双指针来解这道题。我们发现，如果倒数第三个结点走到最后一个结点需要2步，如果倒数第二个结点走到最后一个结点需要1步，因此有这样的规律：从第k个结点开始走到最后一个结点需要走k-1步。我们假设头结点就是“最后一个结点”，因此让一个fast指针走k-1步，此时是链表倒置的第k个结点。而此时两个指针同时走，当发现fast指针走到fast.next值为null时，则找到第k个结点，第k个结点的位置就是slow指针所指向的位置。slow与fast一开始指向head。
图解：
fast走k-1步：

fast与slow同时走，判断条件为fast.next不为null

代码示例：

  1. public ListNode getKthFromEnd(ListNode head, int k) {
  2.         if(head==null) {
  3.             return null;
  4.         }
  5.         if(k<0) {
  6.             return null;
  7.         }
  8.         ListNode fast = head;
  9.         ListNode slow = head;
  10.         while(k-1!=0) {
  11.             fast=fast.next;
  12.             if(fast==null) {
  13.                 return null;
  14.             }
  15.             k--;
  16.         }
  17.         while(fast!=null&&fast.next!=null) {
  18.             fast=fast.next;
  19.             slow=slow.next;
  20.         }
  21.         return slow;
  22.     }

五、合并两个有序链表

对应leetcode题
此处我们设置一个新的头结点，将两个单链表串起来。因为是按照升序来连接链表，因此每次都需要判断l1的值与l2的值谁大谁小，小的先连接。而为了新的头结点不改变，需要另一个指针从头结点开始对l1或者l2连接。因为l1与l2的长度可能不同，因此有可能会先连完一条链，而另一条链直接连在新的链表当中即可。
图解：准备工作：

  1. * public class ListNode {
  2.  *     int val;
  3.  *     ListNode next;
  4.  *     ListNode() {}
  5.  *     ListNode(int val) { this.val = val; }
  6.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  7.  * }
  8.  */
  9. class Solution {
  10.     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
  11.         ListNode newHead = new ListNode();
  12.         ListNode tmp = newHead;
  13.         if(l1==null&&l2==null) {
  14.             return null;
  15.         }
  16.         if(l1==null) {
  17.             newHead.next=l2;
  18.         }
  19.         if(l2==null) {
  20.             newHead.next=l1;
  21.         }
  22.         while(l1!=null&&l2!=null) {
  23.             if(l1.val>l2.val) {
  24.                 tmp.next=l2;
  25.                 l2=l2.next;
  26.                 tmp=tmp.next;
  27.             } else {
  28.                 tmp.next=l1;
  29.                 l1=l1.next;
  30.                 tmp=tmp.next;
  31.             }
  32.         }
  33.         if(l1==null) {
  34.             tmp.next=l2;
  35.         }
  36.         if(l2==null) {
  37.             tmp.next=l1;
  38.         }
  39.         return newHead.next;
  40.     }
  41. }

六、分隔链表

对应leetcode题
为了分开链表中小于val值得结点，我们设置两个新的链表，用空间来换取时间。因此两个新的链表有头结点与临时结点。一边放入小于val值的结点，另一边放入大于和等于val值的结点。但放入结点时有两种情况。第一种情况时第一次放入时，两个新的链表都无指向，因此第一次应该直接指向原来的链表中即可。除了第一次为特殊情况外，新的链表的指针指向的都是原来的链表中cur遍历所指向的该结点。而临时指针也需要向后移一位。而cur也需要后移一位。
需要注意的是：

  1. 如果bs为null则需要改变be的next值为null，否则还会指向某一个结点。
  2. 如果as为null则直接返回bs即可。
  3. 最后将两个新的链表合起来，则需要有ae.next=bs;
    图解：

代码示例：

  1. public ListNode partition(ListNode head, int x) {
  2.         ListNode as = null;
  3.         ListNode ae = null;
  4.         ListNode bs = null;
  5.         ListNode be = null;
  6.         ListNode tmp = head;
  7.         while(tmp!=null) {
  8.             if(tmp.val<x) {
  9.                 if(as==null) {
  10.                     as=tmp;
  11.                     ae=tmp;
  12.                 } else {
  13.                     ae.next=tmp;
  14.                     ae=ae.next;
  15.                 }
  16.             } else {
  17.                 if(bs==null) {
  18.                     bs=tmp;
  19.                     be=tmp;
  20.                 } else {
  21.                     be.next=tmp;
  22.                     be=be.next;
  23.                 }
  24.             }
  25.             tmp=tmp.next;
  26.         }
  27.         if(as==null) {
  28.             return bs;
  29.         }
  30.         ae.next=bs;
  31.         if(bs!=null) {
  32.             be.next=null;
  33.         }
  34.         return as;
  35.     }

七、删除排序链表中的重复元素

对应leetcode题
因为一个链表中重复的元素有多个，并且要求全部删除，则我们需要一个循环来遍历链表并且创建指针cur从头结点开始，判断cur.val==cur.next.val，如果相等则跳过重复的元素。当然此时要注意要判断cur.next一定不能为null，否则cur.next.val会空指针异常。示例如下：

但是tmp需要连接的是第三个结点，因此cur此时还要向后移一位。才有tmp.next=cur;cur=cur.next;tmp=tmp.next但是cur.next已经为null了，因此要退出循环。再将tmp.next=null 。

代码示例：

  1. * public class ListNode {
  2.  *     int val;
  3.  *     ListNode next;
  4.  *     ListNode() {}
  5.  *     ListNode(int val) { this.val = val; }
  6.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  7.  * }
  8.  */
  9. class Solution {
  10.     public ListNode deleteDuplicates(ListNode head) {
  11.         ListNode newHead = new ListNode(-1);
  12.         ListNode cur = head;
  13.         ListNode tmp = newHead;
  14.         while(cur!=null) {
  15.             if(cur.next!=null&&cur.val==cur.next.val) {
  16.                 while(cur.next!=null&&cur.val==cur.next.val) {
  17.                     cur=cur.next;
  18.                 }
  19.                 cur=cur.next;
  20.             } else {
  21.                 tmp.next=cur;
  22.                 cur=cur.next;
  23.                 tmp=tmp.next;
  24.             }
  25.         }
  26.         tmp.next=null;
  27.         return newHead.next;
  28.     }
  29. }

八、判断一个链表是否是回文链表

对应leetcode题
回文链表指的是链表两边的结点的值对称，如果为奇数不用判断中间部分。我们第一步首先创建两个指针slow和fast，让slow走到中间结点的位置，就等同于找中间结点。第二步逆置slow后半部分的链表。就等同于逆置链表，思想上是一样的。第三步是从head结点和slow结点处遍历前半部分与后半部分链表。如果对应结点有不相同的val值，则返回true。
图解：

注意
1.slow走到中间时创建cur指针与curNext指针对链表进行逆置。当slow到达最后一个结点的条件为cur!=null。
2.判断是否是回文链表，则情况有两种。第一种是结点数量为奇数时有head!=slow，第二种是结点数量为偶数时有head.next!=slow。

结点数为偶数时需要判断：如果能够走到head与slow相遇则返回true，否则返回false。

结点数为偶数时需要判断head.next==slow，否则在链表中如果head与slow“擦肩而过”等同于不相遇。

代码示例：

  1. * public class ListNode {
  2.  *     int val;
  3.  *     ListNode next;
  4.  *     ListNode() {}
  5.  *     ListNode(int val) { this.val = val; }
  6.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  7.  * }
  8.  */
  9. class Solution {
  10.     public boolean isPalindrome(ListNode A) {
  11.         if(A==null) {
  12.             return true ;
  13.         }
  14.         ListNode fast = A;
  15.         ListNode slow = A;
  16.         while(fast!=null&&fast.next!=null) {
  17.             fast=fast.next.next;
  18.             slow = slow.next;
  19.         }
  20.         ListNode cur = slow.next;
  21.         while(cur!=null) {
  22.             ListNode curNext = cur.next;
  23.             cur.next=slow;
  24.             slow=cur;
  25.             cur=curNext;
  26.         }
  27.        while(A.val==slow.val) {
  28.            if(A.next==slow||A==slow) {
  29.                return true;
  30.            }
  31.            A=A.next;
  32.            slow=slow.next;
  33.        }
  34.         return false;
  35.     }
  36. }

九、两个链表的第一个公共节点

对应leetcode题
找两个链表的公共结点，首先想到的是先设置两个指针从两个链表的头开始，让相对长的链表先走两个链表的长度差值，再让两个指针一起走，相遇的点就是它们的公共点。我们假设p1指向的始终是较长的链表，p2指向的是较短的链表。因此可以分为三步：第一步求出两个链表的长度的差值；第二步让链表走长度差值步。第三步让两个指针一起走，判断的终点为两个指针相遇。
图解：

代码示例1：这种相对来说好理解一些。

  1. public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  2.         if(headA==null||headB==null) {
  3.             return null;
  4.         }
  5.         ListNode pl = headA;
  6.         ListNode ps = headB;
  7.         int lenA = 0 ;
  8.         int lenB = 0 ;
  9.         while(pl!=null) {
  10.             pl=pl.next;
  11.             lenA++;
  12.         }
  13.         pl=headA;
  14.         while(ps!=null) {
  15.             ps=ps.next;
  16.             lenB++;
  17.         }
  18.         ps=headB;
  19.         int len = lenA-lenB;
  20.         if(len<0) {
  21.             pl=headB;
  22.             ps=headA;
  23.             len = lenB-lenA;
  24.         }
  25.         while(len!=0) {
  26.             pl=pl.next;
  27.             len--;
  28.         }
  29.         while(pl!=ps) {
  30.             pl=pl.next;
  31.             ps=ps.next;
  32.         }
  33.         return pl;
  34.     }

代码示例2：这种代码可读性不太强，但是更加简洁，原理相同。

  1. public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  2.         if (headA == null || headB == null) {
  3.             return null;
  4.         }
  5.         ListNode pA = headA, pB = headB;
  6.         while (pA != pB) {
  7.             pA = pA == null ? headB : pA.next;
  8.             pB = pB == null ? headA : pB.next;
  9.         }
  10.         return pA;
  11.     }

十、判断一个链表是否有环

对应leetcode题
设置两个指针fast和slow，都从头结点处开始走，fast指针一次走两步，slow指针一次走一步，如果最后相遇，则该链表肯定有环。如果fast指针为null，则该链表不是环形链表。
图解：

代码示例：

  1. * class ListNode {
  2.  *     int val;
  3.  *     ListNode next;
  4.  *     ListNode(int x) {
  5.  *         val = x;
  6.  *         next = null;
  7.  *     }
  8.  * }
  9.  */
  10. public class Solution {
  11.     public boolean hasCycle(ListNode head) {
  12.         if(head==null) {
  13.             return false;
  14.         }
  15.         ListNode fast = head;
  16.         ListNode slow = head;
  17.         while(fast!=null&&fast.next!=null) {
  18.             fast=fast.next.next;
  19.             slow=slow.next;
  20.             if(fast==slow) {
  21.                 return true;
  22.             }
  23.         }
  24.         return false;
  25.     }
  26. }

十一、判断一个链表是否有环，并返回第一个结点

对应leetcode题
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果该链表是一个环形链表，则它的形状如下图所示。我们设直线的起始位置为起始点，长度为a，而在走过长度b后在该小圆点处相遇。而长度c等于一个环的周长减去b。因此我们仍然可以设置双指针fast和slow。fast指针一次走两步，slow指针一次走一步。因此slow与fast指针在环中相遇时，fast有可能走了n圈环，而slow最多只可能走了一圈，而fast走的路程又是slow走的路程的两倍。因此有以下公式：fast走的路程=a+n(b+c)+b，而slow走的路程=2(a+b)。因此有a+n(b+c)+b=2(a+b)，化简得a=c+(n−1)(b+c)。因此，当发现 slow 与 fast 相遇时，我们再额外使用一个指针 ptr。起始，它指向链表头部；随后，它和 slow 每次向后移动一个位置。最终，它们会在入环点相遇。（slow可能走很多圈，但是从相遇处开始一步一步走一定会相遇，相遇时返回slow或pte指针即可）。

图解：

代码示例：

  1. * class ListNode {
  2.  *     int val;
  3.  *     ListNode next;
  4.  *     ListNode(int x) {
  5.  *         val = x;
  6.  *         next = null;
  7.  *     }
  8.  * }
  9.  */
  10. public class Solution {
  11.     public ListNode detectCycle(ListNode head) {
  12.         if(head==null) {
  13.             return null;
  14.         }
  15.         ListNode fast = head;
  16.         ListNode slow = head;
  17.         while(fast!=null&&fast.next!=null) {
  18.             fast=fast.next.next;
  19.             slow=slow.next;
  20.             if(fast==slow) {
  21.                 ListNode pre = head;
  22.                 while(pre!=slow) {
  23.                     pre=pre.next;
  24.                     slow=slow.next;
  25.                 }
  26.                 return pre;
  27.             }
  28.         }
  29.         return null;
  30.     }
  31. }

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/ZJRUIII/article/details/121202911

内容来源于网络，如有侵权，请联系作者删除！

Java数据结构leetcode算法链表

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com