链表相关笔试题

本文主要是介绍链表相关笔试题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

链表面试题目

• • 删除链表中给定的结点
  • 链表的反转（逆置链表）
  • 求链表的中间结点
  • 链表的倒数第K个结点
  • 链表的第一个公共结点
  • 分割链表
  • 回文链表
  • 复杂链表的复制

删除链表中给定的结点

leetcode:删除链表中给定的结点

思路：

• 找要删除的结点；
• 改变结点的引用来删除结点（注意区分头结点的删除与非头结点删除的不同）；
  
  

代码实现：

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        //结点为空时
        if(head==null){
            return null;
        }
        ListNode cur=head;
        ListNode prev=null; //prev标记cur的前一个结点
        while(cur!=null){
            if(cur.val==val){
                //删除结点
                //如果是头结点
                if(prev==null){
                    head=cur.next;
                    cur=head;
                }else{
                     //不是头结点 
                    prev.next=cur.next;
                    cur=prev;
                }   
            }else{
                prev=cur;
                cur=cur.next;

            }
        }
       return head;

    }
}

链表的反转（逆置链表）

leetcode:反转链表

思路：

借助三个引用：cur prev next；

遍历链表，同时将当前结点的指向修改为指向它的前一个引用；由于结点没有引用其前一个结点，因此必须事先保存它的前一个结点,在更改引用之前，还需要保存它的后一个结点；

代码实现：

class Solution {
    public ListNode reverseList(ListNode head) {
        //链表为空时
        if(head==null){
            return null;
        }
        ListNode cur=head;
        ListNode prev=null;  //指向当前结点的前一个
        ListNode next=null;  //指向当前结点的后一个

        while(cur!=null){
            //说明结点存在
            //修改之前先保存其后一个结点
            next=cur.next;
            //修改引用
            cur.next=prev;
            prev=cur;
            cur=next;
        }
        return prev;

    }
}

求链表的中间结点

leetcode：链表的中间结点


思路：

借助两个引用：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; //fast每次走两步
            slow=slow.next;  //slow每次走一步
        }
       return slow;
    }
}

思考：

该题目中，当结点个数为偶数时，返回的是后一个结点，如果要返回前一个结点，怎么做？

方法：将slow的前一个结点prev保存起来，当为偶数个结点且要返回前一个时，只需要返回prev即可；
if(fast)=null,return prev; //偶数结点
if(fast)!=null,return slow; //奇数结点

链表的倒数第K个结点

leetcode：链表的倒数第K个结点


思路：
借助两个引用：front back；

• front从起始位置先走K步；
• front与back同时往后走，front为空时结束；
• back的位置刚好就是倒数第K个结点的位置；

图解：

代码实现：

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
         //借助两个引用
         ListNode front=head;
         ListNode back=head;


         //让front先往后走K步
         while(0!=k){
             if(front==null){
                 return null;
             }
             front=front.next;
             k--;
         }

         //让两个引用同时走
        while(front!=null){
            front=front.next; //走一步
            back=back.next; //走一步
        }
      return back;
    }
}

链表的第一个公共结点

leetcode：链表的第一个公共结点

思路：

• 判断是否相交（找最后一个结点—>遍历链表，看是否相等）；
• 求交点；

由题目中已知，链表不带环，不带环的链表相交的三种情况如下所示：

代码实现：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //任意一个链表为空时，均不可能相交
        if(headA==null ||headB==null){
            return null;
        }
        //遍历链表求交点
       //遍历链表A
        ListNode curA=headA;
        int sizeA=1;
        while(curA.next!=null){
            sizeA++;   //遍历一个结点，sizeA增加一个
            curA=curA.next;
        }
       //遍历链表B
        ListNode curB=headB;
        int sizeB=1;
        while(curB.next!=null){
            sizeB++;//遍历一个结点，sizeB增加一个
            curB=curB.next;
        }

        if(curA!=curB){
            return null;
        }

        //上面执行完，肯定会相交
        //求交点
        int gap=sizeA-sizeB;
        curA=headA;
        curB=headB;
        if(gap>=0){
            //A比B长
            while(0!=gap--){
                curA=curA.next;
            }
        }else{
            while(0!=gap++){
                curB=curB.next;
            }

        }
        
        while(curA!=curB){
            curA=curA.next;
            curB=curB.next;
        }

       return curA;
        
    }
}

分割链表

leetcode：分割链表


思路：

• 构造两个带头结点的空链表：lessHead greatHead；
• lessHead用来存放小于给定值的结点， greatHead用来存大于给定值的结点；
• 将lessHead的尾结点指定greatHead的头结点即可（注意是带头的）；

代码实现：

class Solution {
    public ListNode partition(ListNode head, int x) {
        //链表为空时
        if(head==null){
            return null;
        }
    //将lessHead和greatHead给为带头结点的链表
     ListNode lessHead =new ListNode(0); //保存小于特定值的结点
     ListNode tailL= lessHead;

     ListNode greatHead =new ListNode(0); //保存大于特定值的结点
     ListNode tailG =greatHead;

     ListNode cur=head;
     while(cur!=null){
         if(cur.val<x){
             tailL.next=cur;
             tailL=cur;
         }else{
             tailG.next=cur;
             tailG=cur; 
         }
         cur=cur.next;
     }
       //链接链接起来
       //两个都带头结点，所以要指向greatHead.next
       tailL.next=greatHead.next;
       tailG.next=null;
       return lessHead.next;
    }
}

回文链表

leetcode:回文链表

思路：

• 找链表的中间结点，以中间结点将链表分割成head1，head2两个链表；
• 将后一个链表逆置；
• 依次比对两个链表的结点值是否相等；
• 将链表链接起来；

代码实现：

class Solution {
    //找中间结点方法
    public ListNode getMiddleNode(ListNode head){
        ListNode fast=head;
        ListNode slow=head;
        ListNode prev=null;
       //确保fast两次都可以走成功
        while(fast!=null && fast.next!=null){
            fast=fast.next.next;
            prev=slow;
            slow=slow.next;

        }
        if(fast==null){
          return prev;
        }
          return slow;
     
    }
      //逆置链表
 public ListNode reverseList(ListNode head){
     ListNode cur=head;
     ListNode next=null;
     ListNode prev=null;

     while(cur!=null){
         //修改之前先保存next的位置
          next=cur.next;
          //修改引用
          cur.next=prev;
          prev=cur;
          cur=next;
       }
        return prev;
 }

    public boolean isPalindrome(ListNode head) {
        //1.找链表的中间结点
        ListNode mid=getMiddleNode(head);
        ListNode B=mid.next;

        //2.将后一个链表进行逆置
        B= reverseList(B);

        //3. 依次比较两个链表的值域
        ListNode curA=head;
        ListNode curB=B;
        boolean ret=true;
        while(curA!=null && curB!=null){
            if(curA.val!=curB.val){
                ret=false;
                break;
            }
            curA=curA.next;
            curB=curB.next;

        }
        //4.将链表链表链接
        B=reverseList(B);
        mid.next=B;
        return ret;

    }
}

复杂链表的复制

leetcode：复杂链表的复制

思路：

• 在原链表的每个结点后面插入一个与原结点值相等的新结点；
• 给新插入的结点的随机引用赋值；
• 将新插入的结点断开；

插入相同结点的新链表

给每个随机引用赋值

cur在第一个结点时：

插入的结点断开

代码实现：

class Solution {
    public Node copyRandomList(Node head) {
          //链表为空时
        if(head==null){
            return null;
        }
        //1. 在原链表的每个结点后插入值相等的结点
        Node cur=head;
        while(cur!=null){
        //new一个与原结点相同值域的结点
            Node newNode=new Node(cur.val);
            
            newNode.next=cur.next;
            cur.next=newNode;
            cur=newNode.next;
        }

        //2.给新插入的结点的随机引用赋值
        cur=head;
        while(cur!=null){
            Node newNode =cur.next;
            if(cur.random!=null){
                newNode.random=cur.random.next;

            }
            cur=newNode.next;
        }
        
        //将插入结点断开
        Node newHead=head.next;
        cur=head;
        while(cur.next!=null){
            Node curNext=cur.next;
            cur.next=curNext.next;
            cur=curNext;
        }
        return newHead;
    }
}

这篇关于链表相关笔试题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！