• 链表面试常见题

    目录

    1.移除链表元素

    2.反转链表

    3.链表的中间结点

    4.链表中倒数第k个结点

    5.合并两个有序链表 

    6.链表分割

    7.链表的回文结构

    8.相交链表

    9.环形链表

    10.环形链表II

    1.移除链表元素

    链接  203. 移除链表元素 - 力扣（LeetCode）

    题目要求

     分析一下

     上代码

    1. class Solution {
    2.     public ListNode removeElements(ListNode head, int val) {
    3.         if (head == null) return null;
    4.         ListNode prev = head;
    5.         ListNode cur = head.next;
    6.         while(cur != null) {
    7.             if(cur.val == val) {
    8.                 prev.next = cur.next;
    9.                 cur = cur.next;
    10.             }else {
    11.                 prev = cur;
    12.                 cur = cur.next;
    13.             }
    14.         }
    15.         if (head.val == val) {
    16.             head= head.next;
    17.         }
    18.         return head;
    19.     }
    20. }

    2.反转链表

    链接  206. 反转链表 - 力扣（LeetCode）

    题目要求

     分析一下

     上代码

    1. class Solution {
    2.     public ListNode reverseList(ListNode head) {
    3.         if(head == null) return null;//说明链表为空
    4.         if(head.next == null) return head;//说明只有一个节点
    5.  
    6.         ListNode cur = head.next;
    7.         head.next = null;
    8.         while(cur != null) {
    9.             ListNode curNext= cur.next; 
    10.             cur.next = head;
    11.             head =cur;
    12.             cur = curNext;
    13.         }
    14.     return head;
    15.     }
    16. }

    3.链表的中间结点

    链接  876. 链表的中间结点 - 力扣（LeetCode）

    题目要求

    分析一下

     上代码

    4.链表中倒数第k个结点

    链接  链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)

    题目要求

     分析一下

     上代码

    5.合并两个有序链表 

    链接  21. 合并两个有序链表 - 力扣（LeetCode）

    题目要求

     分析一下

    上代码

    1. class Solution {
    2.     public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    3.         ListNode newHead = new ListNode(-1);//傀儡节点 虚拟结点
    4.         ListNode tmp = newHead;
    5.         while(list1 != null && list2 != null) {
    6.             if(list1.val < list2.val) {
    7.                 tmp.next = list1;
    8.                 list1 = list1.next;
    9.                 tmp = tmp.next;
    10.             } else {
    11.                 tmp.next = list2;
    12.                 list2 = list2.next;
    13.                 tmp = tmp.next;
    14.             }
    15.         }
    16.     if(list1 != null) {
    17.         tmp.next = list1;
    18.     }
    19.     if(list2 != null) {
    20.         tmp.next = list2;
    21.     }
    22.     return newHead.next;
    23.     }
    24. }

    6.链表分割

    链接 链表分割_牛客题霸_牛客网 (nowcoder.com)

    题目要求

     分析一下

    上代码

    1. import java.util.*;
    2.  
    3. public class Partition {
    4.     public ListNode partition(ListNode pHead, int x) {
    5.         ListNode bs = null;
    6.         ListNode be = null;
    7.         
    8.         ListNode as = null;
    9.         ListNode ae = null;
    10.         ListNode cur = pHead;
    11.         while(cur != null) {
    12.             if(cur.val < x) {
    13.                 //插入到第一个段
    14.                 if(bs == null) {
    15.                     //这是第一次插入元素
    16.                     bs = cur;
    17.                     be = cur;
    18.                 }else {
    19.                     be.next =cur;
    20.                     be = be.next;
    21.                 }
    22.             } else {
    23.                 //插入到第二个段
    24.                 if(as == null) {
    25.                     as =cur;
    26.                     ae =cur;
    27.                 }else {
    28.                     ae.next =cur;
    29.                     ae = ae.next;
    30.                 }
    31.             }
    32.             cur = cur.next;
    33.         }
    34.         if(bs == null) {
    35.             return as;
    36.         }
    37.         be.next =as; 
    38.         if(as != null) {
    39.             ae.next = null;
    40.         }
    41.         return bs;
    42.     }
    43. }

    7.链表的回文结构

    链接  链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

    题目要求

     分析一下

     上代码

    1. public class PalindromeList {
    2.     public boolean chkPalindrome(ListNode A) {
    3.         // write code here
    4.         if(A == null || A.next == null) {
    5.             return true;
    6.         }
    7.         ListNode fast = A;
    8.         ListNode slow = A;
    9.         //找中点
    10.         while(fast!= null && fast.next != null) {
    11.             fast = fast.next.next;
    12.             slow = slow.next;
    13.         }
    14.         //翻转
    15.         ListNode cur = slow.next;
    16.         while(cur != null) {
    17.             ListNode curNext = cur.next;
    18.             cur.next = slow;
    19.             slow = cur;
    20.             cur = curNext;
    21.         }
    22.         //对比
    23.         while(A != slow) {
    24.             if(A.val != slow.val) {
    25.                 return false;
    26.             }
    27.             //偶数情况下
    28.             if(A.next != slow) { 
    29.                 return true;
    30.             }
    31.             A = A.next;
    32.             slow = slow.next;
    33.         }
    34.         return true;
    35.     }
    36. }

    8.相交链表

    链接  160. 相交链表 - 力扣（LeetCode）

    题目要求

     分析一下

     上代码

    1. public class Solution {
    2.     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    3.         //1.分别求两个链表的长度
    4.         int lenA = 0;
    5.         int lenB = 0;
    6.         ListNode pl = headA;//pl代表永远指向长的链表
    7.         ListNode ps = headB;//ps代表永远指向短的链表
    8.         while(pl != null) {
    9.             lenA++;
    10.             pl = pl.next;
    11.         }
    12.         while(ps != null) {
    13.             lenB++;
    14.             ps = ps.next;
    15.         }
    16.         pl = headA;
    17.         ps = headB;
    18.         //2，求两个链表的差值长度 len一定是一个正数
    19.         int len = lenA -lenB;
    20.         if(len < 0) {
    21.             pl = headB;
    22.             ps = headA;
    23.             len = lenB - lenA;
    24.         }
    25.         //3.让长链表先走差值长度
    26.         while(len != 0) {
    27.             pl = pl.next;
    28.             len--;
    29.         }
    30.         //4.再一块走，相遇
    31.         while(pl != ps && pl != null) {
    32.             pl = pl.next;
    33.             ps = ps.next;
    34.         }
    35.         if(pl == null) {
    36.             return null;
    37.         }
    38.         return pl;
    39.     }
    40. }

    9.环形链表

     链接  141. 环形链表 - 力扣（LeetCode）

    题目要求

    分析一下

    首先，明白什么叫链表带环，

    由链表中的某一个节点，一直找next指针，一定会再次到达这个节点，这样的链表就说是有环的，并且带环的链表每个节点的next 指针，都不为null。

    其次，这道题如果继续考虑使用快慢指针来做，那么快指针fast每次走几步，

    （1）如果快指针fast每次都两步，慢指针slow每次走一步，一定可以相遇

     （2）如果快指针fast每次都走3步，走4步...走n步，不一定可以相遇

     所以只要快指针fast每次走2步，慢指针每次走1步，就一定可以追上，这道题就按这个思路走

    上代码

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

     10.环形链表II

    链接 142. 环形链表 II - 力扣（LeetCode）

    题目要求

     分析一下

     上代码

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

  • 相关阅读:
    大聪明教你学Java | Mysql 为何会引起锁表及其解决办法
    计数排序和排序的稳定性
    java和vue的狱警管理系统监狱系统狱务管理系统
    FPGA - 科学设计复位信号(XILINX)
    C++ 析构函数
    linux的shell编程入门
    python小记3
    长尾效应和肥尾效应
    GFS分布式文件系统
    程序分析与优化 - 2 控制流图
  • 原文地址：https://blog.csdn.net/m0_58761900/article/details/125598727