关于单链表的几个面试题

我们下面的题是在创建好链表环境和一些方法后实现的，也就是说要基于环境，关于这个环境可以看我上一篇博客(39条消息) 无头结点的单链表的实现_咸鱼吐泡泡的博客-CSDN博客

下面直接上题:

1.编写代码，用给定值x为基准将链表分割成两部分，所有小于x的节点排在大于或等于x的节点之前，并且不能打乱顺序。例如原先的链表是[12,17,34,56,14]，现在让小于15的节点放在前面，大于等于15的节点放在后面，结果就是[12,14,17,34,56]。我这里将题的链接放在这里，有兴趣可以做一下 链表分割_牛客题霸_牛客网

思路:

1.首先先判断链表是否为空，是则返回null

2.创建一个辅助变量cur来帮助遍历链表

3.创建动态变化的两个区间，第一个区间为[bs,be] ，第二个区间为[as,ae]，这里的bs、be、as、ae的类型是节点

4.执行分区操作

5.注意事项

    public Node partition(int x) {
        if(headNode==null){
            return null;
        }
        Node bs = null;
        Node be = null;
        Node as = null;
        Node ae = null;
        Node cur = headNode;
        while(cur!=null){
            //分区操作
            if(cur.no 
主函数里面实现一下
 
    public static void main(String[] args) {//验证分割链表
        Linkedlist linkedlist1 = new Linkedlist();
        linkedlist1.finallAdd(12);
        linkedlist1.finallAdd(17);
        linkedlist1.finallAdd(34);
        linkedlist1.finallAdd(56);
        linkedlist1.finallAdd(14);
        Linkedlist.Node node = linkedlist1.partition(15);
        linkedlist1.printList(node);
    }
 
结果
 
 
2.链表的回文结构:例如一个链表为[1,2,3,2,1]这就是一个回文链表
 
* 思路:
* 1.首先先判断链表是否为空，如果为空返回false、判断链表是否只有一个节点，是则返回true
* 2.创建两个辅助变量fast、slow
* 找到中间节点(快慢指针)slow
* 3.创建cur = slow.next;temp;使链表后半截反转，反转条件cur!=null
* 执行反转:temp = cur.next;cur.next = slow;slow = cur;cur = temp;
* 4.判断headNode.no与slow.no是否相等，不相等则返回false，相等则headNode=headNode.next;
    slow = slow.next继续比较
* 当headNode==slow时，返回true
 
 
    public boolean palindromeList(){
        if(headNode==null){
            return false;
        }
        if(headNode.next==null){//链表中只有一个节点，该链表就是回文链表
            return true;
        }
        Node fast = headNode;
        Node slow = headNode;
        //找中间节点slow
        while(fast!=null&&fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        Node cur = slow.next;
        Node temp = null;
        //反转链表后半截
        while(cur!=null){
            temp = cur.next;
            cur.next = slow;
            slow = cur;
            cur = temp;
        }
        //判断是否为回文
        while(headNode!=slow){
            if(headNode.no!=slow.no){
                return false;
            }
            if(headNode.next==slow){//当链表长度为偶数时
                return true;
            }
            headNode = headNode.next;
            slow = slow.next;
        }
        return true;
    }
 
主函数里面实现一下
 
    public static void main(String[] args) {//验证回文链表
        Linkedlist linkedlist1 = new Linkedlist();
        linkedlist1.finallAdd(11);
        linkedlist1.finallAdd(21);
        linkedlist1.finallAdd(11);
        linkedlist1.finallAdd(11);
        boolean b = linkedlist1.palindromeList();
        if(b){
            System.out.println("是回文链表");
        }else{
            System.out.println("不是回文链表");
        }
    }
 
结果
 
 
3.输入两个链表，找出它们的第一个公共节点。
 
力扣
 
看下图
 
 
上面链表headA和headB就有公共节点(这里的公共节点是指节点的地址相同，而不是节点的值相同)
 
思路:快慢指针
 
1.首先先判断两个链表headA、headB是否为空，如果之中一个为空返回null
 
2.计算两个链表的长度，创建两个辅助变量tempA、tempB，让tempA = headA;tempB = headB；分别计算两个链表的长度
 
3.让长度长的链表先走两个长度的差值，随后判断tempA是否与tempB相等，不相等则tempA = tempA.next;tempB = tempB.next;
 
4.最后返回tempA
 
    public static Linkedlist.Node getIntersectionNode(
            Linkedlist.Node headA, Linkedlist.Node headB) {
        if(headA==null||headB==null){
            return null;
        }
        Linkedlist.Node tempA = headA;//这里先假定链表headA要长一些，让tempA始终指向长的链表
        Linkedlist.Node tempB = headB;
        int countA = 0;
        int countB = 0;
        //计算两个链表长度
        while(tempA!=null){
            countA++;
            tempA = tempA.next;
        }
        while(tempB!=null){
            countB++;
            tempB = tempB.next;
        }
        tempA = headA;
        tempB = headB;
        int len = countA-countB;
        while(len>0){//让长的链表先走长度的差值
            tempA = tempA.next;
            len--;
        }
        while(len<0){//让长的链表先走长度的差值
            tempB = tempB.next;
            len++;
        }
        while(tempA!=tempB){
            tempA = tempA.next;
            tempB = tempB.next;
        }
        return tempA;
    }
 
 主函数里面实现一下
 
    public static Linkedlist.Node getIntersectionNode(
            Linkedlist.Node headA, Linkedlist.Node headB) {
        if(headA==null||headB==null){
            return null;
        }
        Linkedlist.Node tempA = headA;//这里先假定链表headA要长一些，让tempA始终指向长的链表
        Linkedlist.Node tempB = headB;
        int countA = 0;
        int countB = 0;
        //计算两个链表长度
        while(tempA!=null){
            countA++;
            tempA = tempA.next;
        }
        while(tempB!=null){
            countB++;
            tempB = tempB.next;
        }
        tempA = headA;
        tempB = headB;
        int len = countA-countB;
        while(len>0){//让长的链表先走长度的差值
            tempA = tempA.next;
            len--;
        }
        while(len<0){//让长的链表先走长度的差值
            tempB = tempB.next;
            len++;
        }
        while(tempA!=tempB){
            tempA = tempA.next;
            tempB = tempB.next;
        }
        return tempA;
    }
    public static void intersection(Linkedlist.Node headA, Linkedlist.Node headB){//人为制造交点
        headA.next.next = headB.next.next;
    }
    public static void main(String[] args) {//验证两链表的公共节点
        Linkedlist linkedlist1 = new Linkedlist();
        linkedlist1.finallAdd(12);
        linkedlist1.finallAdd(17);
        linkedlist1.finallAdd(34);
        linkedlist1.finallAdd(56);
        linkedlist1.finallAdd(14);
        linkedlist1.printList();
        System.out.println();
        System.out.println("=====================");
        Linkedlist linkedlist2 = new Linkedlist();
        linkedlist2.finallAdd(12);
        linkedlist2.finallAdd(17);
        linkedlist2.finallAdd(34);
        linkedlist2.finallAdd(56);
        linkedlist2.finallAdd(14);
        linkedlist2.printList();
        System.out.println();
        intersection(linkedlist1.headNode,linkedlist2.headNode);
        System.out.println("交点是"+getIntersectionNode(linkedlist1.headNode, linkedlist2.headNode).no);
    }
 
结果
 
 
 如果不人为制造交点，两个链表是独立的，肯定是没交点的
 
4.给定一个链表，判断链表中是否有环力扣
 
思路：快慢指针
 
1.首先判断链表是否为空，是则返回false
 
2.创建两个辅助变量fast、slow来遍历链表，fast每次走两步，slow每次走一步。当fast==slow时返回true跳出循环
 
3.当循环条件不满足时，则说明链表没环
 
    public boolean hasCycle(Node head) {
        if(head==null){
            return false;
        }
        Node fast = head;
        Node slow = head;
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }
    //人为制造环
    public void creatcycle(){
        Node temp = headNode;
        while(temp.next!=null){//遍历原先的链表找到最后一个节点
            temp = temp.next;
        }
        temp.next = headNode.next.next;//让最后一个节点的next链表头的第三个节点
    }
 
在主函数里面实现一下
 
    public static void main(String[] args) {//测试链表是否有环
        Linkedlist linkedlist1 = new Linkedlist();
        linkedlist1.finallAdd(12);
        linkedlist1.finallAdd(13);
        linkedlist1.finallAdd(14);
        linkedlist1.finallAdd(15);
        linkedlist1.creatcycle();
        boolean flag = linkedlist1.hasCycle(linkedlist1.headNode);
        if(flag){
            System.out.println("有环");
        }else{
            System.out.println("没环");
        }
    }
 
结果
 
 
 
 
5.给定一个链表，返回链表开始的第一个节点。如果链表无环，则返回null力扣 
 
 思路：快慢指针
 
* 1.首先先判断链表是否为空，是则返回null
* 2.创建两个辅助变量fast、slow。fast每次走两步，slow每次走一步，如果有环fast比slow先入环
* (1)设起点到入环点的距离为x
* (2)设环的周长为c
* (3)设相遇点到环入口点的距离为y
* 当两个fast和slow相遇之后，因为fast的速度是slow的2倍，所以此时fast走过的路程是slow的2倍，则有下列函数关系
* fast走的路程:x+c+c-y;
* slow走的路程:x+c-y
* 则:2*(x+c-y) = x+c+c-y,解的x = y,也即是说此时将solw = headNode,和fast一起走以相同的速度运动，当fast==slow时，该位置的节点就是环的入口点。
* 也有可能环很小，fast在环里面转了很多圈，slow才入圈，然后fast在追击slow。此时的函数关系就是2*(x+c-y) = x+n*c+c-y,解得x = (n-1)*c+y。
* 也就是说此时的x很大，x！=y。但是没关系，我们让slow = headNode走x的距离，此时的slow和fast一定会相遇
 
    public Node detectCycle(Node head) {
        if(head==null){
            return null;
        }
        Node fast = head;
        Node slow = head;
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast==slow){//说明有环
                break;
            }
        }
        //判断此时出来的是有环还是没环
        if(fast==null||fast.next==null){//没环
            return null;
        }
        slow = head;
        while(slow!=fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
    //人为制造环
    public void creatcycle(){
        Node temp = headNode;
        while(temp.next!=null){//遍历原先的链表找到最后一个节点
            temp = temp.next;
        }
        temp.next = headNode.next.next;//让最后一个节点的next链表头的第三个节点
    }
 
主函数里面实现一下
 
    public static void main(String[] args) {//测试链表是否有环,并测试环的入口节点
        Linkedlist linkedlist1 = new Linkedlist();
        linkedlist1.finallAdd(12);
        linkedlist1.finallAdd(13);
        linkedlist1.finallAdd(14);
        linkedlist1.finallAdd(15);
        linkedlist1.creatcycle();
        boolean flag = linkedlist1.hasCycle(linkedlist1.headNode);
        if(flag){
            System.out.println("有环");
            System.out.println("环的入口节点是"+linkedlist1.detectCycle(linkedlist1.headNode).no);
        }else{
            System.out.println("没环");
        }
    }
 
结果