单链表经典题目合集

Tony__Ferguson

已于 2025-04-22 17:48:00 修改

阅读量820

点赞数 18

文章标签：数据结构链表

于 2025-04-15 17:23:48 首次发布

本文链接：https://blog.csdn.net/Tony__Ferguson/article/details/147249288

版权

1.移除链表中所有key==value的节点

题目链接：https://leetcode.cn/problems/remove-linked-list-elements
思路：首先考虑特殊情况：链表为空，那就直接返回null.如果不为空。
如果链表不为空就开始正式解题：！首先我们怎么删除节点?删除一个节点就是将欲删除节点的上一个节点的next设置为欲删除节点的next,问题在于这时单链表，我们没有prev域，很难找上一个节点，我们可以反其道行之：首先定义一个cur节点等于head,然后定义一个curN=cur.next;然后让curN去遍历整个链表，如果curN.val==val,那么就cur.next=curN.next,这样就相当于cur是prev域，但是还有个小问题，就是curN是从第二个节点开始判断的，头节点也有可能是欲删除节点，那么我们只需在遍历结束后判断head.val,如果要删，那就head=head.next;即可，
具体代码实现：

public ListNode removeElements(ListNode head, int val) {
//非空检验
        if(head==null){
            return null;
        }
        ListNode cur=head;//相当于curN的prev域
       ListNode curN=cur.next;
        while(curN!=null){
            if(curN.val==val){
                cur.next=curN.next;
                curN=curN.next;     
            }
            else{
                cur=curN;
                curN=curN.next;
            }
        }
        //判断头节点
        if(head.val==val){
            head=head.next;
        }
        return head; 
    }

2.反转一个单链表

题目链接：https://leetcode.cn/problems/reverse-linked-list
思路：看似困难，实则十分简单，首先我们讨论链表为空或者只有一个节点，那也用不着反转，直接返回原头节点就可以，如果不是，我们直接从第二个节点开始将其一个个头插到头节点就完事，也就是定义一个cur=head.next,将cur一个个头插到头节点，直到cur为空，但是注意头插的过程会改变cur的next，所以我们还需每次循环定义一个curN=cur.next,头插完之后通过cur=curN的方式遍历整个链表。
具体代码如下：

 public ListNode reverseList(ListNode head) {
 //链表为空或者只有一个节点
 if(head==null||head.next==null){
 return head;}
ListNode cur=head.next;
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
思路：很经典的快慢指针问题，我们把链表看成一条线段，线段的起点有一个点叫fast和一个点叫slow，我们假设fast一次走两步，slow一次走一步，也就是说fast速度是slow的两倍，那么当fast走到线段终点时slow在哪里？显而易见在中点！但是我们还是要排除下特殊情况：当链表只有一个节点直接返回头节点就可以。
具体代码实现：

 public ListNode middleNode(ListNode head) {
 //链表只有一个节点
 if(head.next==null){
 return head;}
 ListNode fast=head;
 ListNode slow=head;
 while(fast!=null&&fast.next!=null){
 fast=fast.next.next;//一次走两步
 slow=slow.next;}//一次走一步
 return slow;     
 }

补充：while循环条件一定是两个都要满足，如果不加条件1，看图：
在这里插入图片描述
fast上次走完已经为空，我进行fast.next判断时就会造成空指针异常，因为null.anything都是不可以的，所以我们每次都要对fast本身进行非空判断。

4.输入一个链表，输出该链表中倒数第k个结点的值

题目链接：https://leetcode.cn/problems/kth-node-from-end-of-list-lcci
思路：其实也是用快慢指针来做，我们可以结合图来看：
在这里插入图片描述
我们反着看：目标节点跟尾节点的距离其实就是k-1!我们让fast先走k-1步，然后俩一起走，当fast到达尾节点的时候，slow必然就在目标节点上。因为这样的话，fast和slow的距离始终是k-1,当fast到达尾节点，slow也就正好到目标节点。听不懂别急，我还有历史版本：
说是如何让我军扎营到距敌军的二十里处，范将军这时就说：先派一支小部队行军二十里，随后大军和小部队同步行军，当小部队遇到敌军时也就意味着大军距离敌军距离正好二十里。
具体代码如下：

 public int kthToLast(ListNode head, int k) {
 if(head.next==null){
 return head;}
 ListNode fast=head;
 ListNode slow=head;
 //先让小部队走k-1距离
  for(int i=0;i<k-1;i++){
 fast=fast.next;
 }
 //一起走直到小部队碰到敌军
 while(fast!=null&&fast.next!=null){
 fast=fast.next;
 slow=slow.next;
 }
 返回目标节点的值
 return slow.val;
 }

5.将两个有序链表合并为一个新的有序链表

题目链接：https://leetcode.cn/problems/merge-two-sorted-lists
思路：不要想复杂，就是一个比大小的题目，首先特殊情况：两个表都为空，那就直接返回null我们首先创建一个节点newH作为排序后的新链表的头节点，然后创建一个替死鬼cur节点指向newH，随后开始对表1和表2的比较，通过遍历整个链表的方式，list1.val<list2.val,那我就把list1作为newH的下一个节点，然后让list1往前走一步，反之亦然，直到其中一个表为空。我们把它写进循环，循环条件就是两个表都不为空，所以当循环结束也就意味着一个表空了，那剩下的就更好办了，我们直接让cur.next指向剩下那个表，因为两个表本身是有序的。可以结合本王独家思路图看（专门做给你看的喵）（看到这真的不三连我的博客吗宝宝宝宝宝宝）：
在这里插入图片描述
具体代码实现：

  public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
  //两个链表都为空
  if(list1==null&&list2==null){
  return null;
  }
  //合并后的链表的头节点
  ListNode newH=new ListNode();
  ListNode cur=newH;//替死鬼节点
  while(list1!=null&&list2!=null){
  if(list1.val<=list2.val){
  cur.next=list1;
  list1=list1.next;
  cur=cur.next;}
  else{
  cur.next=list2;
  list2=list2.next;
  cur=cur.next;}
  }
  //循环结束，说明有一个表为空了
  //用if判断是哪个空
  if(list1==null){
  cur.next=list2;}
 
  if(list2==null){
  cur.next=list1;} 
return newH.next;
}

6.以x值为基准分割链表

题目链接：https://leetcode.cn/problems/partition-list
思路：我们可以创建两个小链表，一个链表放小于x的节点，一个链表放大于等于x的节点，最后我们只需将两个链表“连接”起来即可，具体看图：
在这里插入图片描述
具体代码实现：

   if(head==null){//链表为空
            return null;}
        ListNode sb=null;//小段开始   
        ListNode se=null;//小段结束
        ListNode bb=null;//大段开始
        ListNode be=null;//大段结束
        ListNode cur=head;
        while(cur!=null) {
            //放在小段
            if (cur.val < x) {
                //第一次放
                if (sb == null) {
                    sb = se = cur;
                }
                //不是第一次放
                else{
                    se.next=cur;
                    se=se.next;
                }
            }
            //放在大段
            else{
                //第一次放
                if(bb==null){
                    bb=be=cur;
                }
                //不是第一次放
                else{
                    be.next=cur;
                    be=be.next;
                }
            }
             cur=cur.next;

            }
        //如果小段为空
        if(sb==null){
            return bb;
        }
        //如果大段为空
        if(bb==null){
            return sb;
        }
        se.next=bb;
        if(be!=null){
            be.next=null;
        }
        return sb;

补充：看着很复杂其实逻辑很简单，把be.next置为空是为了防止环的出现。

7.判断链表是否回文

题目链接：https://leetcode.cn/problems/palindrome-linked-list
思路;判断链表是不是回文很简单：我们让首节点和尾节点都同时往前走：一旦出现值不相等就返回false，不然就继续往前走，如果直到相遇还没返回false那就是回文链表，但是！这是单链表没有prev域，所以为了让尾节点能往前走，我们首先需要对后半部分进行反转，具体步骤如下：1.找到中间节点 2.反转后半部分节点 3.开始比较。具体代码实现如下：

 public ListNode reverseList(ListNode head) {
 //链表为空
 if(head==null){
 return true;}
 //找到中间节点
 ListNode fast=head;
 ListNode slow=head;
 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(head!=slow){
if(head.val!=slow.val){
return false;}
head=head.next;
if(head==slow){
return true;}//若总节点个数为奇数，防止完美错过。
slow=slow.next;}
return true;
}

8.求链表相交节点

题目链接：https://leetcode.cn/problems/intersection-of-two-linked-lists
思路：首先我们找到相对较长的的那个链表，求出两个链表的长度差值，让较长的链表先走差值步，然后两个链表一起走，直到它们相交或者为空，为空就返回null。
具体代码实现：

 public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode pl=headA;
ListNode ps=headB;
int A=0;
int B=0;
while(pl!=null){
A++;
pl=pl.next;}
while(ps!=null){
B++;
ps=ps.next;}
int data=A-B;
if(data>0){
pl=headA;
ps=headB;}
else{//神来之笔，保证pl一定指向长的链表
pl=headB;
ps=headA;
data=B-A;}//神来之笔，保证data是正数
while(data!=0){
    pl=pl.next;
    data--;
}
while(pl!=ps){
if(ps==null){//俩链表不相交
return null;} 
pl=pl.next;
ps=ps.next;}
return pl;     
    }

9.判断链表是否有环

题目链接：https://leetcode.cn/problems/linked-list-cycle
思路：利用快慢指针，我们让fast一次走两步，slow一次走一步，如果链表中有环那么最终他们俩肯定能相遇，但是如果没有环，那么fast最后一定为空，为空就返回false。
具体代码如下：

 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;
}

结束！